oj.uz

답안 #572194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572194 2022-06-04T00:05:25 Z teki 수열 (APIO14_sequence) C++11
0 / 100
 16 ms 3380 KB 
#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();

            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 (turn != 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;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:78: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]
   78 |             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;
      |                       ^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB contestant didn't find the optimal answer: 20168074 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 624 KB contestant didn't find the optimal answer: 1788154876 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 3380 KB declared answer doesn't correspond to the split scheme: declared = 1308241056, real = 9898175648
2 Halted 0 ms 0 KB -