General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
187240381 Practice:
ShivanshJ
1763E - 24 C++20 (GCC 11-64) Time limit exceeded on test 13 2000 ms 22008 KB 2022-12-30 15:29:25 2022-12-30 15:29:25
→ 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;
vector<int>dp[MAX][2];
bool cmp(vector<int>&a,vector<int>&b) {
    if(a[0]!=b[0]) {
        return a[0]<b[0];
    }
    return a[0]*a[0]-a[1] > b[0]*b[0]-b[1];
}
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[i][0]={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[i][curr]=dp[i][curr^1];
            if(i-(j*(j-1))/2>=0) {
                vector<int>res=dp[i-(j*(j-1))/2][curr];
                res[0]+=j;
                res[1]+=j*j;
                if(cmp(res,dp[i][curr])) {
                    dp[i][curr]=res;
                }
            }
        }
    }
    int sq=dp[p][curr][1],sum=dp[p][curr][0];
    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