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