Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

 
 
 
 
Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
187240832 Дорешивание:
ShivanshJ
1763E - 24 C++20 (GCC 11-64) Полное решение 296 мс 3144 КБ 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;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования