# |
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 |
|
//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;
}
Click to see test details