oj.uz

Submission #248882

# Submission time Handle Problem Language Result Execution time Memory
248882 2020-07-13T16:41:54 Z ryansee Wombats (IOI13_wombats) C++14
55 / 100
 955 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 {
	ll dp[203][203];
	node*l,*r;
	node(int s,int e){
		int m=(s+e)>>1;
		if(s^e) l=new node(s,m),r=new node(m+1,e), combine(s,e,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(ll s,ll e,node* l, node* r){
		ll m=(s+e)>>1;
		FOR(i,0,M-1)FOR(j,0,M-1)dp[i][j]=INF;
		vector<ll> gaps={0,M-1};
		DEC(d,M-1,0){
			vector<ll> ngaps;
			assert(M-1-d+2==siz(gaps));
			FOR(i,0,M-1-d){
				ll j=i+d;
				ll opt=-1, best=INF;
				FOR(k,gaps[i],gaps[i+1]){
					ll val=l->dp[i][k]+r->dp[k][j]+C[m][k];
					if(val<best)best=val,opt=k;
				}
				assert(~opt);
				dp[i][j]=best, ngaps.eb(opt);
			}
			gaps=ngaps;
			gaps.eb(M-1);
			gaps.insert(gaps.begin(), 0);
		}
		gaps={0,M-1};
		DEC(d,M-1,1){
			vector<ll> ngaps;
			assert(M-1-d+2==siz(gaps));
			FOR(i,d,M-1){
				ll j=i-d;
				ll opt=-1, best=INF;
				FOR(k,gaps[i-d],gaps[i-d+1]){
					ll val=l->dp[i][k]+r->dp[k][j]+C[m][k];
					if(val<best)best=val,opt=k;
				}
				assert(~opt);
				dp[i][j]=best, ngaps.eb(opt);
			}
			gaps=ngaps;
			gaps.eb(M-1);
			gaps.insert(gaps.begin(), 0);
		}
	}
	void update(ll s,ll e,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;
		}
		ll m=(s+e)>>1;
		if(x>m)r->update(m+1,e,x);else l->update(s,m,x);
		combine(s,e,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(0,n-1,P);
}

void changeV(int P, int Q, int W) {
    /* ... */
    C[P][Q]=W;
    seg->update(0,n-1,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 43 ms 75384 KB Output is correct
2 Correct 50 ms 75384 KB Output is correct
3 Correct 140 ms 77048 KB Output is correct
4 Correct 43 ms 75384 KB Output is correct
5 Correct 43 ms 75384 KB Output is correct
6 Correct 6 ms 8320 KB Output is correct
7 Correct 8 ms 8320 KB Output is correct
8 Correct 6 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 5 ms 8320 KB Output is correct
3 Correct 5 ms 8320 KB Output is correct
4 Correct 9 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 7 ms 8960 KB Output is correct
9 Correct 7 ms 8960 KB Output is correct
10 Correct 7 ms 9088 KB Output is correct
11 Correct 92 ms 10104 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 204 ms 24696 KB Output is correct
2 Correct 179 ms 24696 KB Output is correct
3 Correct 212 ms 24824 KB Output is correct
4 Correct 207 ms 24824 KB Output is correct
5 Correct 197 ms 24824 KB Output is correct
6 Correct 6 ms 8320 KB Output is correct
7 Correct 5 ms 8320 KB Output is correct
8 Correct 6 ms 8320 KB Output is correct
9 Correct 760 ms 24896 KB Output is correct
10 Correct 6 ms 8320 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 79316 KB Output is correct
2 Correct 51 ms 79352 KB Output is correct
3 Correct 49 ms 79352 KB Output is correct
4 Correct 87 ms 80120 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 24824 KB Output is correct
2 Correct 185 ms 24696 KB Output is correct
3 Correct 221 ms 24824 KB Output is correct
4 Correct 223 ms 24824 KB Output is correct
5 Correct 209 ms 24824 KB Output is correct
6 Correct 47 ms 79352 KB Output is correct
7 Correct 51 ms 79352 KB Output is correct
8 Correct 50 ms 79352 KB Output is correct
9 Correct 87 ms 80120 KB Output is correct
10 Correct 43 ms 75384 KB Output is correct
11 Correct 43 ms 75384 KB Output is correct
12 Correct 126 ms 77048 KB Output is correct
13 Correct 44 ms 75384 KB Output is correct
14 Correct 44 ms 75384 KB Output is correct
15 Correct 6 ms 8320 KB Output is correct
16 Correct 5 ms 8320 KB Output is correct
17 Correct 5 ms 8320 KB Output is correct
18 Correct 6 ms 9088 KB Output is correct
19 Correct 7 ms 9088 KB Output is correct
20 Correct 6 ms 9088 KB Output is correct
21 Correct 6 ms 9088 KB Output is correct
22 Correct 6 ms 8960 KB Output is correct
23 Correct 7 ms 8960 KB Output is correct
24 Correct 7 ms 9088 KB Output is correct
25 Correct 89 ms 10108 KB Output is correct
26 Correct 6 ms 9088 KB Output is correct
27 Correct 776 ms 24892 KB Output is correct
28 Runtime error 541 ms 262144 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 213 ms 24824 KB Output is correct
2 Correct 173 ms 24696 KB Output is correct
3 Correct 214 ms 24824 KB Output is correct
4 Correct 220 ms 24952 KB Output is correct
5 Correct 208 ms 24824 KB Output is correct
6 Correct 48 ms 79352 KB Output is correct
7 Correct 48 ms 79360 KB Output is correct
8 Correct 48 ms 79352 KB Output is correct
9 Correct 86 ms 80120 KB Output is correct
10 Correct 42 ms 75384 KB Output is correct
11 Correct 44 ms 75384 KB Output is correct
12 Correct 122 ms 77048 KB Output is correct
13 Correct 43 ms 75384 KB Output is correct
14 Correct 43 ms 75416 KB Output is correct
15 Runtime error 955 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -