답안 #22991 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22991	2017-05-01T03:01:32 Z	model_code	Hacker (BOI15_hac)	C++11	100 / 100	706 ms	25164 KB

/*
    Task: Hacker
    Model Solution 1
    Author: Krzysztof Kiljan
    Complexity: O(n log n)
    Uses set to calculate maximum on all ranges
 */

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define REP(I,N) for(int I=0;I<(N);I++)
#define PB push_back
#define MP make_pair
#define ST first
#define ND second


typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long ll;

const int MAXN = 500013;
VI v;

int n, m, k, operCompNum, myCompNum;

// sums[i] = v[i] + ... v[i +myCompNum -1]
VI sums;

//Holds pairs <value, index in sums array>
set <PII> curSums;

void readInput()
{
    scanf("%d", &n);

    operCompNum = n / 2;
    myCompNum = n - operCompNum;

    REP(i, n)
    {
        scanf("%d", &k);
        v.PB(k);
    }
}

//makes   v -> vvv, for easier further implementation

void duplicateV()
{
    REP(j, 2)
    REP(i, n)
    v.push_back(v[i]);
}

// Precomputes sum of values of computers in range <start, start + myCompNum)
// for all starts possible
void precompSums()
{
    int sum = 0;
    int curStart = 0;
    int end = curStart + myCompNum;

    for (int i = curStart; i < end; i++)
        sum += v[i];

    sums.PB(sum);

    while (curStart < 2 * n)
    {
        sum -= v[curStart];
        curStart++;
        sum += v[end];
        end++;
        sums.PB(sum);
    }
}

PII calcMaxAns()
{
    int curStart = n - myCompNum + 1;
    int end = curStart + myCompNum;
    PII ans = MP(-1, -1);

    for (int i = curStart; i < end; i++)
        curSums.insert(MP(sums[i], i));

    ans = *(curSums.begin());

    while (end < 2 * n)
    {
        curSums.erase(MP(sums[curStart], curStart));
        curStart++;
        curSums.insert(MP(sums[end], end));
        end++;

        if (ans.ST < (*(curSums.begin())).ST)
        {
            ans = *(curSums.begin());
        }
    }

    return ans;
}

int solve()
{
    precompSums();
    PII ans = calcMaxAns();

    return ans.ST;
}

int main()
{
    readInput();
    duplicateV();
    int ans = solve();
    printf("%d\n", ans);
    return 0;
}

Compilation message

hac.cpp: In function 'void readInput()':
hac.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
hac.cpp:48:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k);
                        ^

Subtask #1
20.0 / 20.0

#	결과	메모리	Grader output
1	Correct	1176 KB	Output is correct
2	Correct	1176 KB	Output is correct
3	Correct	1176 KB	Output is correct
4	Correct	1176 KB	Output is correct
5	Correct	1176 KB	Output is correct
6	Correct	1176 KB	Output is correct
7	Correct	1176 KB	Output is correct
8	Correct	1176 KB	Output is correct
9	Correct	1176 KB	Output is correct
10	Correct	1176 KB	Output is correct
11	Correct	1176 KB	Output is correct
12	Correct	1176 KB	Output is correct
13	Correct	1176 KB	Output is correct
14	Correct	1176 KB	Output is correct
15	Correct	1176 KB	Output is correct
16	Correct	1176 KB	Output is correct
17	Correct	1176 KB	Output is correct
18	Correct	1176 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1176 KB	Output is correct
2	Correct	0 ms	1176 KB	Output is correct
3	Correct	0 ms	1176 KB	Output is correct
4	Correct	0 ms	1176 KB	Output is correct
5	Correct	0 ms	1176 KB	Output is correct
6	Correct	0 ms	1176 KB	Output is correct
7	Correct	0 ms	1176 KB	Output is correct
8	Correct	0 ms	1176 KB	Output is correct
9	Correct	0 ms	1176 KB	Output is correct
10	Correct	0 ms	1176 KB	Output is correct
11	Correct	0 ms	1176 KB	Output is correct
12	Correct	0 ms	1176 KB	Output is correct
13	Correct	0 ms	1176 KB	Output is correct
14	Correct	0 ms	1176 KB	Output is correct
15	Correct	0 ms	1176 KB	Output is correct
16	Correct	0 ms	1176 KB	Output is correct
17	Correct	0 ms	1176 KB	Output is correct
18	Correct	0 ms	1176 KB	Output is correct
19	Correct	0 ms	1176 KB	Output is correct
20	Correct	0 ms	1176 KB	Output is correct
21	Correct	0 ms	1176 KB	Output is correct
22	Correct	0 ms	1316 KB	Output is correct
23	Correct	3 ms	1448 KB	Output is correct
24	Correct	0 ms	1316 KB	Output is correct
25	Correct	0 ms	1448 KB	Output is correct
26	Correct	3 ms	1448 KB	Output is correct
27	Correct	0 ms	1176 KB	Output is correct
28	Correct	0 ms	1176 KB	Output is correct
29	Correct	0 ms	1176 KB	Output is correct
30	Correct	0 ms	1448 KB	Output is correct
31	Correct	0 ms	1448 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1176 KB	Output is correct
2	Correct	0 ms	1176 KB	Output is correct
3	Correct	3 ms	1448 KB	Output is correct
4	Correct	56 ms	5156 KB	Output is correct
5	Correct	206 ms	12088 KB	Output is correct
6	Correct	266 ms	13144 KB	Output is correct
7	Correct	286 ms	16448 KB	Output is correct
8	Correct	706 ms	25164 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1176 KB	Output is correct
2	Correct	0 ms	1176 KB	Output is correct
3	Correct	0 ms	1176 KB	Output is correct
4	Correct	0 ms	1176 KB	Output is correct
5	Correct	0 ms	1176 KB	Output is correct
6	Correct	0 ms	1176 KB	Output is correct
7	Correct	0 ms	1176 KB	Output is correct
8	Correct	0 ms	1176 KB	Output is correct
9	Correct	0 ms	1176 KB	Output is correct
10	Correct	0 ms	1176 KB	Output is correct
11	Correct	0 ms	1176 KB	Output is correct
12	Correct	0 ms	1176 KB	Output is correct
13	Correct	0 ms	1176 KB	Output is correct
14	Correct	0 ms	1176 KB	Output is correct
15	Correct	0 ms	1176 KB	Output is correct
16	Correct	0 ms	1176 KB	Output is correct
17	Correct	0 ms	1176 KB	Output is correct
18	Correct	0 ms	1176 KB	Output is correct
19	Correct	0 ms	1176 KB	Output is correct
20	Correct	0 ms	1176 KB	Output is correct
21	Correct	0 ms	1176 KB	Output is correct
22	Correct	0 ms	1316 KB	Output is correct
23	Correct	3 ms	1448 KB	Output is correct
24	Correct	0 ms	1316 KB	Output is correct
25	Correct	0 ms	1448 KB	Output is correct
26	Correct	3 ms	1448 KB	Output is correct
27	Correct	0 ms	1176 KB	Output is correct
28	Correct	0 ms	1176 KB	Output is correct
29	Correct	0 ms	1176 KB	Output is correct
30	Correct	0 ms	1448 KB	Output is correct
31	Correct	0 ms	1448 KB	Output is correct
32	Correct	0 ms	1176 KB	Output is correct
33	Correct	0 ms	1176 KB	Output is correct
34	Correct	3 ms	1448 KB	Output is correct
35	Correct	56 ms	5156 KB	Output is correct
36	Correct	206 ms	12088 KB	Output is correct
37	Correct	266 ms	13144 KB	Output is correct
38	Correct	286 ms	16448 KB	Output is correct
39	Correct	706 ms	25164 KB	Output is correct
40	Correct	3 ms	1648 KB	Output is correct
41	Correct	9 ms	2168 KB	Output is correct
42	Correct	16 ms	2676 KB	Output is correct
43	Correct	189 ms	12088 KB	Output is correct
44	Correct	603 ms	25164 KB	Output is correct
45	Correct	73 ms	6672 KB	Output is correct
46	Correct	269 ms	16448 KB	Output is correct
47	Correct	686 ms	25164 KB	Output is correct
48	Correct	333 ms	25164 KB	Output is correct
49	Correct	336 ms	25164 KB	Output is correct
50	Correct	329 ms	25164 KB	Output is correct

답안 #22991

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 40.0 / 40.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
40.0 / 40.0