oj.uz

Submission #22992

# Submission time Handle Problem Language Result Execution time Memory
22992 2017-05-01T03:02:04 Z model_code Hacker (BOI15_hac) C++11
40 / 100
 1000 ms 2792 KB 
/*
    Task: Hacker
    Slow solution 1
    Author: Krzysztof Kiljan
    Complexity: O(n^2)

    For every start position i, calculates the maximum protection operator can
    get and subtracts it from sum of all values. The result is max over all of these values
 */

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

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, sumAll;

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

    operCompNum = n / 2;

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

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

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


// First calculates sum of values of computers in range <start, start + operCompNum)
// than moves the range by one until end would reach position of start cyclically
int calcOperProtection(int start)
{
    int sum = 0;
    int ans = 0;
    int end = start + operCompNum;
    int curStart = start;

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

    ans = max(ans, sum);

    while (end < start + n - 1)
    {
        sum -= v[curStart];
        curStart++;
        sum += v[end];
        end++;
        ans = max(ans, sum);
    }

    return ans;
}

// Calculates the value hacker will get assuming he will start at computer number nr
// Numbers in <0, n)

int tryStart(int nr)
{
    int res = calcOperProtection(1 + nr);
    return sumAll - res;
}

int solve()
{
    int ans = 0;

    REP(i, n)
    ans = max(ans, tryStart(i));

    return ans;
}

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

Compilation message

hac.cpp: In function 'void readInput()':
hac.cpp:37:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
hac.cpp:43: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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1172 KB Output is correct
3 Correct 0 ms 1172 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1172 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
9 Correct 0 ms 1172 KB Output is correct
10 Correct 0 ms 1172 KB Output is correct
11 Correct 0 ms 1172 KB Output is correct
12 Correct 0 ms 1172 KB Output is correct
13 Correct 0 ms 1172 KB Output is correct
14 Correct 0 ms 1172 KB Output is correct
15 Correct 0 ms 1172 KB Output is correct
16 Correct 0 ms 1172 KB Output is correct
17 Correct 0 ms 1172 KB Output is correct
18 Correct 0 ms 1172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1172 KB Output is correct
3 Correct 0 ms 1172 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1172 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
9 Correct 0 ms 1172 KB Output is correct
10 Correct 0 ms 1172 KB Output is correct
11 Correct 0 ms 1172 KB Output is correct
12 Correct 0 ms 1172 KB Output is correct
13 Correct 0 ms 1172 KB Output is correct
14 Correct 0 ms 1172 KB Output is correct
15 Correct 0 ms 1172 KB Output is correct
16 Correct 0 ms 1172 KB Output is correct
17 Correct 0 ms 1172 KB Output is correct
18 Correct 0 ms 1172 KB Output is correct
19 Correct 0 ms 1172 KB Output is correct
20 Correct 0 ms 1172 KB Output is correct
21 Correct 0 ms 1172 KB Output is correct
22 Correct 6 ms 1312 KB Output is correct
23 Correct 19 ms 1312 KB Output is correct
24 Correct 6 ms 1312 KB Output is correct
25 Correct 19 ms 1312 KB Output is correct
26 Correct 19 ms 1312 KB Output is correct
27 Correct 0 ms 1172 KB Output is correct
28 Correct 0 ms 1172 KB Output is correct
29 Correct 0 ms 1172 KB Output is correct
30 Correct 19 ms 1312 KB Output is correct
31 Correct 19 ms 1312 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1172 KB Output is correct
3 Correct 19 ms 1312 KB Output is correct
4 Execution timed out 1000 ms 2792 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1172 KB Output is correct
3 Correct 0 ms 1172 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1172 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
9 Correct 0 ms 1172 KB Output is correct
10 Correct 0 ms 1172 KB Output is correct
11 Correct 0 ms 1172 KB Output is correct
12 Correct 0 ms 1172 KB Output is correct
13 Correct 0 ms 1172 KB Output is correct
14 Correct 0 ms 1172 KB Output is correct
15 Correct 0 ms 1172 KB Output is correct
16 Correct 0 ms 1172 KB Output is correct
17 Correct 0 ms 1172 KB Output is correct
18 Correct 0 ms 1172 KB Output is correct
19 Correct 0 ms 1172 KB Output is correct
20 Correct 0 ms 1172 KB Output is correct
21 Correct 0 ms 1172 KB Output is correct
22 Correct 6 ms 1312 KB Output is correct
23 Correct 19 ms 1312 KB Output is correct
24 Correct 6 ms 1312 KB Output is correct
25 Correct 19 ms 1312 KB Output is correct
26 Correct 19 ms 1312 KB Output is correct
27 Correct 0 ms 1172 KB Output is correct
28 Correct 0 ms 1172 KB Output is correct
29 Correct 0 ms 1172 KB Output is correct
30 Correct 19 ms 1312 KB Output is correct
31 Correct 19 ms 1312 KB Output is correct
32 Correct 0 ms 1172 KB Output is correct
33 Correct 0 ms 1172 KB Output is correct
34 Correct 19 ms 1312 KB Output is correct
35 Execution timed out 1000 ms 2792 KB Execution timed out
36 Halted 0 ms 0 KB -