oj.uz

Submission #248877

# Submission time Handle Problem Language Result Execution time Memory
248877 2020-07-13T15:51:55 Z ryansee Wombats (IOI13_wombats) C++14
55 / 100
 8909 ms 262148 KB 
#include "wombats.h"

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=int; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

// #define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
ll n, M, H[5003][203], C[5003][203];
struct node {
	int s,e,m;
	ll dp[203][203];
	node*l,*r;
	node(int S,int E){
		s=S,e=E,m=(s+e)>>1;
		if(s^e) l=new node(s,m),r=new node(m+1,e), combine(l,r);
		else {
			FOR(i,0,M-1) FOR(j,i,M-1) if(i^j) dp[i][j]=dp[i][j-1]+H[s][j-1]; else dp[i][j]=0;
			FOR(i,0,M-1) FOR(j,0,i-1) dp[i][j]=dp[j][i];
		}
	}
	void combine(node* l, node* r){
		FOR(i,0,M-1)FOR(j,0,M-1){
			dp[i][j]=INF;
			FOR(k,0,M-1) dp[i][j]=min(dp[i][j],l->dp[i][k]+r->dp[k][j]+C[m][k]);
		}
	}
	void update(int x){
		if(s==e){
			FOR(i,0,M-1) FOR(j,i,M-1) if(i^j) dp[i][j]=dp[i][j-1]+H[s][j-1]; else dp[i][j]=0;
			FOR(i,0,M-1) FOR(j,0,i-1) dp[i][j]=dp[j][i];
			return;
		}
		if(x>m)r->update(x);else l->update(x);
		combine(l,r);
	}
}*seg;
void init(int _r, int _c, int HH[5000][200], int VV[5000][200]) {
    /* ... */
    n=_r, M=_c;
    FOR(i,0,4999)FOR(j,0,199)H[i][j]=HH[i][j],C[i][j]=VV[i][j];
    seg=new node(0, n-1);
}

void changeH(int P, int Q, int W) {
    /* ... */
    H[P][Q]=W;
    seg->update(P);
}

void changeV(int P, int Q, int W) {
    /* ... */
    C[P][Q]=W;
    seg->update(P+1);
}

int escape(int V1, int V2) {
    return seg->dp[V1][V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 75384 KB Output is correct
2 Correct 55 ms 75384 KB Output is correct
3 Correct 123 ms 78200 KB Output is correct
4 Correct 42 ms 75384 KB Output is correct
5 Correct 50 ms 75368 KB Output is correct
6 Correct 6 ms 8320 KB Output is correct
7 Correct 6 ms 8320 KB Output is correct
8 Correct 7 ms 8320 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8320 KB Output is correct
2 Correct 6 ms 8320 KB Output is correct
3 Correct 6 ms 8320 KB Output is correct
4 Correct 6 ms 9088 KB Output is correct
5 Correct 7 ms 9088 KB Output is correct
6 Correct 7 ms 9088 KB Output is correct
7 Correct 7 ms 9088 KB Output is correct
8 Correct 9 ms 8960 KB Output is correct
9 Correct 6 ms 8960 KB Output is correct
10 Correct 6 ms 9088 KB Output is correct
11 Correct 94 ms 11384 KB Output is correct
12 Correct 7 ms 9088 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1128 ms 24928 KB Output is correct
2 Correct 1090 ms 24824 KB Output is correct
3 Correct 1099 ms 25080 KB Output is correct
4 Correct 1100 ms 25080 KB Output is correct
5 Correct 1076 ms 25080 KB Output is correct
6 Correct 6 ms 8320 KB Output is correct
7 Correct 6 ms 8320 KB Output is correct
8 Correct 6 ms 8320 KB Output is correct
9 Correct 4918 ms 24988 KB Output is correct
10 Correct 7 ms 8320 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 79352 KB Output is correct
2 Correct 44 ms 79352 KB Output is correct
3 Correct 45 ms 79352 KB Output is correct
4 Correct 89 ms 80760 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1119 ms 24800 KB Output is correct
2 Correct 1107 ms 24856 KB Output is correct
3 Correct 1123 ms 24952 KB Output is correct
4 Correct 1125 ms 24976 KB Output is correct
5 Correct 1109 ms 24952 KB Output is correct
6 Correct 44 ms 79352 KB Output is correct
7 Correct 44 ms 79352 KB Output is correct
8 Correct 44 ms 79352 KB Output is correct
9 Correct 94 ms 80828 KB Output is correct
10 Correct 41 ms 75384 KB Output is correct
11 Correct 41 ms 75388 KB Output is correct
12 Correct 122 ms 78200 KB Output is correct
13 Correct 42 ms 75384 KB Output is correct
14 Correct 46 ms 75392 KB Output is correct
15 Correct 6 ms 8320 KB Output is correct
16 Correct 6 ms 8320 KB Output is correct
17 Correct 6 ms 8320 KB Output is correct
18 Correct 7 ms 9088 KB Output is correct
19 Correct 7 ms 9088 KB Output is correct
20 Correct 7 ms 9088 KB Output is correct
21 Correct 7 ms 9088 KB Output is correct
22 Correct 7 ms 9008 KB Output is correct
23 Correct 7 ms 8960 KB Output is correct
24 Correct 7 ms 9088 KB Output is correct
25 Correct 93 ms 11384 KB Output is correct
26 Correct 7 ms 9088 KB Output is correct
27 Correct 4998 ms 24968 KB Output is correct
28 Runtime error 2370 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 24696 KB Output is correct
2 Correct 1100 ms 24812 KB Output is correct
3 Correct 1140 ms 25080 KB Output is correct
4 Correct 1120 ms 25208 KB Output is correct
5 Correct 1104 ms 25080 KB Output is correct
6 Correct 45 ms 79352 KB Output is correct
7 Correct 44 ms 79352 KB Output is correct
8 Correct 45 ms 79352 KB Output is correct
9 Correct 85 ms 80760 KB Output is correct
10 Correct 42 ms 75384 KB Output is correct
11 Correct 43 ms 75512 KB Output is correct
12 Correct 125 ms 78264 KB Output is correct
13 Correct 43 ms 75388 KB Output is correct
14 Correct 40 ms 75392 KB Output is correct
15 Runtime error 8909 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -