이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define MS(x,y) memset((x),(y),sizeof((x)))
#define MN 1000000001
using namespace std;
int main()
{
#if LOCAL_DEBUG
fstream cin("in.txt");
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
int niza[n];
for (int i = 0; i<n; i++) cin>>niza[i];
int ideal = 0;
for (int i = 0; i<n; i++) ideal += niza[i];
ideal /= (k+1);
set<int> podelbi;
podelbi.insert(n-1);
int res = 0;
vector<int> kadeRes;
for (int ctr = 1; ctr<=k; ctr++) {
vector<pair<pair<int,int>,int>> site;
/// start, end, zbir!
auto itPod = podelbi.begin();
int zbir = 0, s = 0;
for (int j = 0; j<n; j++) {
zbir += niza[j];
if (*itPod == j) {
site.pb({{s,j},zbir});
s = j+1;
zbir = 0;
itPod++;
}
}
int ctr2 = 0, l = site[0].first.first, r = site[0].first.second, zb = site[0].second;
vector<pair<pair<int,int>,int>> mozni[ctr];
int zbMont = 0;
for (int j = 0; j<n; j++) {
if (r < j) {
ctr2++;
l = site[ctr2].first.first;
r = site[ctr2].first.second;
zb = site[ctr2].second;
zbMont = 0;
}
zbMont += niza[j];
if (j != r) mozni[ctr2].pb({{zbMont-ideal,(zb-zbMont)*zbMont},j});
}
vector<pair<int,int>> vistina;
for (int j = 0; j<ctr; j++) sort(mozni[j].begin(),mozni[j].end());
for (int j = 0; j<ctr; j++) {
int turn = mozni[j].size();
if (turn == 0) continue;
for (int kb = 0; kb<mozni[j].size(); kb++) {
if (mozni[j][kb].first.first >= 0) {
turn = kb;
break;
}
}
int fin = min(turn,(int)mozni[j].size()-1);
if (fin-1 >= 0 && mozni[j][turn-1].first.second > mozni[j][turn].first.second) fin--;
vistina.pb({mozni[j][fin].first.second, mozni[j][fin].second});
}
sort(vistina.rbegin(), vistina.rend());
podelbi.insert(vistina[0].second);
res += vistina[0].first;
kadeRes.pb(vistina[0].second);
}
cout<<res<<endl;
for (auto it:kadeRes) cout<<it+1<<" ";
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int main()':
sequence.cpp:79:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int kb = 0; kb<mozni[j].size(); kb++) {
| ~~^~~~~~~~~~~~~~~~
sequence.cpp:55:23: warning: variable 'l' set but not used [-Wunused-but-set-variable]
55 | int ctr2 = 0, l = site[0].first.first, r = site[0].first.second, zb = site[0].second;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |