Submission #378312

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
378312	2021-03-16 12:56:55	couplefire	Toll (BOI17_toll)	C++17	100 / 100	181 ms	14808 KiB

toll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define MAXN 50005
#define INF 1000000009
int ckmin(int &a, int b){return (b<a)?a=b:a;}
int ckmax(int &a, int b){return (b>a)?a=b:b;}
vector<pair<pair<int, int>, int>> adj[MAXN][5];
int p, n, m, q;
vector<pair<pair<int, int>, int>> queries;
int ans[MAXN];
int mxlvl;
void cdq(int l, int r, vector<pair<pair<int, int>, int>> &bruh){
    if(r < l) return;
    int mid = (l+r)/2;
    int dp[r-l+1][p][p];
    for(int i = l; i<=r; i++){
        for(int a = 0; a<p; a++) for(int b = 0; b<p; b++) dp[i-l][a][b] = INF;
    }
    for(int a = 0; a<p; a++) for(int b = 0; b<p; b++) dp[mid-l][a][b] = (a == b)?0:INF;
    for(int i = mid+1; i<=r; i++){
        for(int a = 0; a<p; a++){
            for(int b = 0; b<p; b++){
                for(auto x : adj[i-1][b]) ckmin(dp[i-l][a][x.first.second], dp[i-1-l][a][b]+x.second);
            }
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44