Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
187240832 Practice:
ShivanshJ
1763E - 24 C++20 (GCC 11-64) Accepted 296 ms 3144 KB 2022-12-30 15:34:01 2022-12-30 15:34:01
→ Source
                    //Enjoying CP as always!
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MAX = 2e5+5;
const int MAXN = 650;
const int INF = 1e6;
const int MOD = 1e9+7;
pair<int,int>dp[2][MAX];
bool cmp(pair<int,int>&a,pair<int,int>&b) {
    if(a.first!=b.first) {
        return a.first<b.first;
    }
    return a.first*a.first-a.second > b.first*b.first-b.second;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int p;
    cin>>p;
    int curr=0;
    for(int i=0;i<=p;i++) {
        dp[0][i]={INF,INF};
    }
    dp[0][0]={0,0}; //nodes , square
    for(int j=1;j<MAXN;j++) {
        curr^=1;
        for(int i=0;i<=p;i++) {
            dp[curr][i]=dp[curr^1][i];
            if(i-(j*(j-1))/2>=0) {
                pair<int,int>res=dp[curr][i-(j*(j-1))/2];
                res.first+=j;
                res.second+=j*j;
                if(cmp(res,dp[curr][i])) {
                    dp[curr][i]=res;
                }
            }
        }
    }
    int sq=dp[curr][p].second,sum=dp[curr][p].first;
    cout<<sum<<" "<<(sum*sum-sq)/2;
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details