Submission #764140

#TimeUsernameProblemLanguageResultExecution timeMemory
764140NothingXDWombats (IOI13_wombats)C++17
76 / 100
20030 ms71352 KiB
#include "wombats.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef complex<ld> point; void debug_out(){cerr << endl;} template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cout << H << ' '; debug_out(T...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 5e3 + 10; const int maxm = 200 + 10; const int sq = 50; const int inf = 1e9; int n, m, h[maxn][maxm], v[maxn][maxm], dp[maxn][maxm], val[100][maxm][maxm], seg[410][maxm][maxm]; void change(int v, int l, int r, int idx){ if (l + 1 == r){ for (int i = 0; i < m; i++){ for (int j = 0; j < m; j++){ seg[v][i][j] = val[l][i][j]; } } return; } int mid = (l + r) >> 1; if (idx < mid){ change(v << 1, l, mid, idx); } else{ change(v << 1 | 1, mid, r, idx); } for (int i = 0; i < m; i++){ for (int j = 0; j < m; j++){ seg[v][i][j] = inf; for (int k = 0; k < m; k++){ seg[v][i][j] = min(seg[v][i][j], seg[v << 1][i][k] + seg[v << 1 | 1][k][j] + ::v[mid*sq-1][k]); } } } } inline void update(int r){ for (int i = 1; i < m; i++){ dp[r][i] = min(dp[r][i], dp[r][i-1] + h[r][i-1]); } for (int i = m-2; ~i; i--){ dp[r][i] = min(dp[r][i], dp[r][i+1] + h[r][i]); } } inline void build(int blc){ for (int i = 0; i < m; i++){ for (int j = 0; j < m; j++){ if (i == j) dp[blc*sq][j] = 0; else dp[blc*sq][j] = inf; } update(blc*sq); int idx = min((blc+1)*sq, n) - 1; for (int j = blc*sq+1; j <= idx; j++){ for (int k = 0; k < m; k++){ dp[j][k] = dp[j-1][k] + v[j-1][k]; } update(j); } for (int j = 0; j < m; j++){ val[blc][i][j] = dp[idx][j]; } } change(1, 0, (n-1)/sq+1, blc); } void init(int R, int C, int H[5000][200], int V[5000][200]) { n = R, m = C; for (int i = 0; i < n; i++){ for (int j = 0; j < m-1; j++){ h[i][j] = H[i][j]; } } for (int i = 0; i < n-1; i++){ for (int j = 0; j < m; j++){ v[i][j] = V[i][j]; } } for (int i = 0; i <= (n-1)/sq; i++){ build(i); } } void changeH(int P, int Q, int W) { h[P][Q] = W; build(P/sq); } void changeV(int P, int Q, int W) { v[P][Q] = W; build(P/sq); } int escape(int V1, int V2) { return seg[1][V1][V2]; }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...