제출 #1272954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272954		duckindog	Shortcut (IOI16_shortcut)	C++20	38 / 100	2093 ms	424 KiB

shortcut

#include <bits/stdc++.h>

#include "shortcut.h"

using namespace std;

const long long MAX = 1'000'000'000'000'000'000;

const int N = 500 + 10;
long long pref[N];
inline long long dist(int i, int j) { 
    if (i > j) swap(i, j);
    return pref[j] - pref[i]; 
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    for (int i = 1; i < n; ++i) pref[i] = pref[i - 1] + l[i - 1];
    
    long long answer = MAX;
    for (int st = 0; st < n; ++st) { 
        for (int ed = st + 1; ed < n; ++ed) { 
            long long ret = -MAX;

            long long ma = -MAX;
            deque<int> q;
            for (int i = 0, it = 0; i < n; ++i) { 
                for (; it < i && dist(i, ed) + c + dist(st, it) <= dist(it, i); ++it) { 
                    ma = max(ma, c + dist(st, it) + d[it]);
                }
                while (q.size() && q.front() < it) q.pop_front();

                ret = max(ret, ma + dist(i, ed) + d[i]);
                if (q.size()) ret = max(ret, dist(i, q.front()) + d[i] + d[q.front()]);

                while (q.size() && dist(i, i) + d[i] >= dist(i, q.back()) + d[q.back()]) q.pop_back();
                q.push_back(i);
            }
        
            ma = -MAX;
            for (int i = n - 1, it = n - 1; i >= 0; --i) { 
                for (; it > i && dist(i, st) + c + dist(ed, it) <= dist(i, it); --it) { 
                    ma = max(ma, c + dist(ed, it) + d[it]);
                }

                ret = max(ret, ma + dist(i, st) + d[i]);
            }

            answer = min(answer, ret);
        }
    }

    return answer;
}

컴파일 시 표준 에러 (stderr) 메시지

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3