Submission #812668

#	Time	Username	Problem	Language	Result	Execution time	Memory
812668		eltu0815	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	6577 ms	1277316 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int N;
const int MX = 25;
int pos[MX][400001][8];
ll sum[MX][400001][8], mx[MX][400001][8];

int tmp1[400001];
ll tmp2[400001], tmp3[400001];

vector<ll> T;
void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
    N = n;
    vector<int> tmp = S;
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    
    int cur = tmp.front(); T.push_back(tmp.front());
    while(cur < tmp.back()) {
        auto it = upper_bound(tmp.begin(), tmp.end(), cur);
        T.push_back(*it); cur = *it; cur <<= 1;
    }
    T.push_back((ll)(1e16));
    
    for(int j = 0; j < (int)T.size(); ++j) {
        for(int i = 0; i < N; ++i) {
            pos[j][i][0] = T[j] <= S[i] ? L[i] : W[i];
            sum[j][i][0] = T[j] <= S[i] ? P[i] : S[i];
            mx[j][i][0] = T[j] <= S[i] ? -S[i] : -(ll)(1e16);
        }
        pos[j][N][0] = N, sum[j][N][0] = 0;
    }
    for(int k = 0; k < (int)T.size(); ++k) for(int j = 1; j <= 7; ++j) {
        for(int i = 0; i <= N; ++i) {
            pos[k][i][j] = pos[k][pos[k][i][j - 1]][j - 1];
            sum[k][i][j] = sum[k][pos[k][i][j - 1]][j - 1] + sum[k][i][j - 1];
            mx[k][i][j] = max(mx[k][i][j - 1], sum[k][i][j - 1] + mx[k][pos[k][i][j - 1]][j - 1]);
            tmp1[i] = pos[k][i][j], tmp2[i] = sum[k][i][j], tmp3[i] = mx[k][i][j];
        }
        
        for(int i = 0; i <= N; ++i) {
            mx[k][i][j] = max(tmp3[i], tmp2[i] + tmp3[tmp1[i]]);
            sum[k][i][j] = tmp2[tmp1[i]] + tmp2[i];
            pos[k][i][j] = tmp1[tmp1[i]];
        }
        for(int i = 0; i <= N; ++i) tmp1[i] = pos[k][i][j], tmp2[i] = sum[k][i][j], tmp3[i] = mx[k][i][j];        
        
        for(int i = 0; i <= N; ++i) {
            mx[k][i][j] = max(tmp3[i], tmp2[i] + tmp3[tmp1[i]]);
            sum[k][i][j] = tmp2[tmp1[i]] + tmp2[i];
            pos[k][i][j] = tmp1[tmp1[i]];
        }
        for(int i = 0; i <= N; ++i) tmp1[i] = pos[k][i][j], tmp2[i] = sum[k][i][j], tmp3[i] = mx[k][i][j];        
        
        for(int i = 0; i <= N; ++i) {
            mx[k][i][j] = max(tmp3[i], tmp2[i] + tmp3[tmp1[i]]);
            sum[k][i][j] = tmp2[tmp1[i]] + tmp2[i];
            pos[k][i][j] = tmp1[tmp1[i]];
        }
    }
	return;
}

long long simulate(int x, int z) {
    ll ans = z;
    for(int k = 0; k < (int)T.size() - 1; ++k) {
        for(int j = 7; j >= 0; --j) for(int t = 0; t < 15; ++t) {
            if(!(pos[k][x][j] == N || mx[k][x][j] + ans >= 0ll)) ans += sum[k][x][j], x = pos[k][x][j];
            else break;
        }
        if(ans < T[k]) ans += sum[k][x][0], x = pos[k][x][0];
        if(x == N) return ans;
    }
    
    for(int j = 7; j >= 0; --j) {
        for(int t = 0; t < 15; ++t) if(pos[T.size() - 1][x][j] != N) ans += sum[T.size() - 1][x][j], x = pos[T.size() - 1][x][j];
    }
    ans += sum[T.size() - 1][x][0], x = pos[T.size() - 1][x][0];
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11