oj.uz

Submission #404029

# Submission time Handle Problem Language Result Execution time Memory
404029 2021-05-13T17:06:33 Z PedroBigMan Wombats (IOI13_wombats) C++14
55 / 100
 3104 ms 262148 KB 
#include "wombats.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}

vector<vector<ll> > v,h; ll R,C;
vector<vector<vector<ll> > > d;
vector<ll> up; vector<ll> ps; vector<ll> val1,val2; 

void CalcDist(ll s)
{
	REP(i,0,C) {up[i]=INF;} up[s]=0; 
	ll sum,val;
	REP(r,0,R)
	{
		sum=0LL; ps[0]=0; REP(i,0,C-1) {sum+=h[r][i]; ps[i+1]=sum;}	
		val=INF;
		REP(i,0,C) {val1[i]=val; val=min(val,up[i]-ps[i]);}
		val=INF;
		for(ll i=C-1;i>=0;i--) {val2[i]=val; val=min(val,up[i]+ps[i]);}
		REP(i,0,C) 
		{
			d[s][r][i]=min(up[i],min(val1[i]+ps[i],val2[i]-ps[i])); if(r!=R-1) {up[i]=d[s][r][i]+v[r][i];}
		}			
	}
}

void init(int r, int c, int H[5000][200], int V[5000][200]) 
{
    R=(ll) r; C = (ll) c; vector<ll> xx; REP(i,0,C-1) {xx.pb(0);} REP(i,0,R) {h.pb(xx);} xx.pb(0LL); REP(i,0,R-1) {v.pb(xx);}
	REP(i,0,R) {REP(j,0,C-1) {h[i][j]=H[i][j];}} 
	REP(i,0,R-1) {REP(j,0,C) {v[i][j]=V[i][j];}}
	vector<vector<ll> > grid; REP(i,0,R) {grid.pb(xx);} REP(i,0,C) {d.pb(grid);}
	REP(i,0,C) {up.pb(INF);} REP(i,0,C) {ps.pb(0LL); val1.pb(0LL); val2.pb(0LL);}
	REP(i,0,C) {CalcDist(i);}
	return;
}

void changeH(int p, int q, int W) 
{
    h[p][q]=W; REP(i,0,C) {CalcDist(i);}
}

void changeV(int p, int q, int W) 
{
   	v[p][q]=W; REP(i,0,C) {CalcDist(i);}
}

int escape(int v1, int v2) 
{
   	return d[v1][R-1][v2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
wombats.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5132 KB Output is correct
2 Correct 28 ms 5132 KB Output is correct
3 Correct 107 ms 7816 KB Output is correct
4 Correct 30 ms 5132 KB Output is correct
5 Correct 27 ms 5132 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 2 ms 300 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 84 ms 2780 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 8916 KB Output is correct
2 Correct 591 ms 8664 KB Output is correct
3 Correct 617 ms 8908 KB Output is correct
4 Correct 613 ms 9000 KB Output is correct
5 Correct 639 ms 8780 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 3104 ms 8992 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 9548 KB Output is correct
2 Correct 82 ms 9564 KB Output is correct
3 Correct 82 ms 9548 KB Output is correct
4 Correct 126 ms 10764 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 8912 KB Output is correct
2 Correct 605 ms 8664 KB Output is correct
3 Correct 636 ms 8996 KB Output is correct
4 Correct 622 ms 9028 KB Output is correct
5 Correct 605 ms 8772 KB Output is correct
6 Correct 87 ms 9528 KB Output is correct
7 Correct 82 ms 9548 KB Output is correct
8 Correct 80 ms 9548 KB Output is correct
9 Correct 124 ms 10776 KB Output is correct
10 Correct 30 ms 5132 KB Output is correct
11 Correct 29 ms 5116 KB Output is correct
12 Correct 118 ms 7716 KB Output is correct
13 Correct 27 ms 5132 KB Output is correct
14 Correct 28 ms 5132 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 436 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 82 ms 2720 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 3030 ms 8996 KB Output is correct
28 Runtime error 267 ms 262148 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 8916 KB Output is correct
2 Correct 623 ms 8664 KB Output is correct
3 Correct 623 ms 9016 KB Output is correct
4 Correct 611 ms 9024 KB Output is correct
5 Correct 613 ms 8780 KB Output is correct
6 Correct 87 ms 9548 KB Output is correct
7 Correct 80 ms 9548 KB Output is correct
8 Correct 83 ms 9532 KB Output is correct
9 Correct 138 ms 10732 KB Output is correct
10 Correct 29 ms 5132 KB Output is correct
11 Correct 28 ms 5132 KB Output is correct
12 Correct 113 ms 7840 KB Output is correct
13 Correct 28 ms 5132 KB Output is correct
14 Correct 27 ms 5132 KB Output is correct
15 Runtime error 347 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -