oj.uz

Submission #1025101

# Submission time Handle Problem Language Result Execution time Memory
1025101 2024-07-16T15:58:54 Z slivajan Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 344 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long un;
typedef vector<un> vuc;


#define REP(i, a, b) for(un i = a; i < b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

un spocti_kartac(int n, std::vector<int> l, std::vector<int> d, un start, un smer){

    un ptr = start;
    un ret = 0;

    un soucet = 0;

    while((ptr >= 0) and (ptr < n)){
        ret = max(ret, soucet + d[ptr]);
        if (smer == 1) soucet += l[ptr];
        else if (smer == -1) soucet += l[ptr-1];

        ptr += smer;
    }

    return ret;

}

tuple<vuc, vuc> change_to_loop(int n, std::vector<int> l, std::vector<int> d, int c, int a, int b){

    un new_n = b-a+1;

    vuc new_l (new_n);
    vuc new_d (new_n);

    REP(i, 0, new_n-1){
        new_l[i] = l[a+i];
        new_d[i] = d[a+i];
    }

    new_l[new_n-1] = c;
    new_d[new_n-1] = d[a+new_n-1];

    new_d[0] = max(new_d[0], spocti_kartac(n, l, d, a, -1));
    new_d[new_n-1] = max(new_d[new_n-1], spocti_kartac(n, l, d, b, 1));
    
    return {new_l, new_d};

}

un eval_loop(int n, std::vector<un> l, std::vector<un> d){

    un celkovy = 0;
    REP(i, 0, n) celkovy += l[i];

    un ret = 0;

    REP(i, 0, n){
        un j = (i+1) % n;
        un soucet = l[i];

        while(j != i){
            ret = max(ret, d[i] + d[j] + min(soucet, celkovy-soucet));
            soucet += l[j];
            j = (j+1) %n;
        }
    }

    return ret;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    un ret = 0;

    REP(a, 0, n) REP(b, a+1, n) {
        vuc loop_l, loop_n;
        tie(loop_l, loop_n) = change_to_loop(n, l, d, c, a, b);
        ret = max(ret, eval_loop((un)loop_l.size(), loop_l, loop_n));
    }

    return ret;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB n = 4, incorrect answer: jury 80 vs contestant 110
2 Halted 0 ms 0 KB -