제출 #1283466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283466		Leyna	Shortcut (IOI16_shortcut)	C++20	23 / 100	2096 ms	416 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct prefix_sums{
    vector<ll> sums;
    prefix_sums(int n, vector<int> nums){
        sums = vector<ll>(n);
        for (int i=1; i<n; i++){
            sums[i] = sums[i-1] + nums[i-1];
        }
    }
    ll query(int l, int r){
        if (r < l) swap(l, r);
        return sums[r] - sums[l];
    }
};

ll calc_dist(ll start, ll end, ll i, ll j, ll c, prefix_sums sums, vector<int> d){
    ll dist = sums.query(start, end) + d[start] + d[end]; // ohne Express Strecke
    dist = min(dist, sums.query(start, i) + c + sums.query(j, end) + d[start] + d[end]);
    swap(i, j);
    dist = min(dist, sums.query(start, i) + c + sums.query(j, end) + d[start] + d[end]);
    return dist;
}

ll find_diameter (int n, prefix_sums sums, vector<int> d, int i_express, int j_express, ll c){
    ll diameter_len = 0;
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            diameter_len = max(diameter_len, calc_dist(i, j, i_express, j_express, c, sums, d));
        }
    }
    /*ll start = 0, diameter_len = 0;
    for (int i=1; i<n; i++){
        ll dist = calc_dist(0, i, i_express, j_express, c, sums, d);
        cerr << i << ": " << dist << endl;
        if (dist > diameter_len){
            start = i;
            diameter_len = dist;
        }
    }
    cerr << start << endl;
    for (int i=0; i<n; i++){
        if (i == start) continue;
        ll dist = calc_dist(start, i, i_express, j_express, c, sums, d);
        if (dist > diameter_len){
            diameter_len = dist;
        }
    }*/
    //if (left_diameter > right_diameter) swap(left_diameter, right_diameter);
    return diameter_len;
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    prefix_sums sums = prefix_sums(n, l);
    ll best_result = 1e18;
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            //cerr << i << ", " << j << ": " << endl;
            //cerr << find_diameter(n, sums, d, i, j, c) << endl;
            best_result = min(best_result, find_diameter(n, sums, d, i, j, c));
        }
    }
    //cerr << find_diameter(n, sums, d, 0, 6, c);
    return best_result;
}

컴파일 시 표준 에러 (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: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3