oj.uz

Submission #399125

# Submission time Handle Problem Language Result Execution time Memory
399125 2021-05-05T10:39:49 Z ACmachine Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26120 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
int r, c;
vector<vector<int>> v;
vector<vector<int>> h;
struct row{
    vector<int> dp;
    row(){}
    row(vector<int> &init){
        dp.resize(c);
        REP(i, c)
            dp[i] = init[i];
    }
    void normalize(int row_id){
        REP(j, dp.size()){
            REP(i, dp.size()){
                if(i > 0){
                    dp[i] = min(dp[i], dp[i - 1] + h[row_id][i - 1]);
                }
                if(i < (int)dp.size() - 1){
                    dp[i] = min(dp[i], dp[i + 1] + h[row_id][i]);
                }
            }
        }
    }
};
row merge(row &a, row &b, int row_id){ // b je nizsie; row_id = id bcka
    row res = b;
    REP(i, a.dp.size()){
        res.dp[i] += a.dp[i] + v[row_id - 1][i];
    }
    res.normalize(row_id);
    return res;
}
//vector<row> rows;
void go(row &a, int row_id){
    REP(i, a.dp.size()){
        a.dp[i] += v[row_id - 1][i];
    }
    a.normalize(row_id);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R; c = C;
    h.resize(r, vector<int>(c));
    v.resize(r, vector<int>(c));
    REP(i, r - 1){
        REP(j, c){
            v[i][j] = V[i][j];
        }
    }
    REP(i, r){
        REP(j, c - 1){
            h[i][j] = H[i][j];
        }
    }
    //rows.resize(r);
    //vector<int> init(c, 0);
    //REP(i, r){
        //rows[i] = row(init);
    //}
    /* ... */
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    /* ... */
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    /* ... */
}

int escape(int V1, int V2) {
    vector<int> f(c, INF);
    f[V1] = 0;
    row a(f);
    a.normalize(0);
    FOR(i, 1, r, 1){
        go(a, i);
    }
    return a.dp[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: In member function 'void row::normalize(int)':
wombats.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
wombats.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
wombats.cpp:69:9: note: in expansion of macro 'REP'
   69 |         REP(j, dp.size()){
      |         ^~~
wombats.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
wombats.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
wombats.cpp:70:13: note: in expansion of macro 'REP'
   70 |             REP(i, dp.size()){
      |             ^~~
wombats.cpp: In function 'row merge(row&, row&, int)':
wombats.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
wombats.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
wombats.cpp:83:5: note: in expansion of macro 'REP'
   83 |     REP(i, a.dp.size()){
      |     ^~~
wombats.cpp: In function 'void go(row&, int)':
wombats.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
wombats.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
wombats.cpp:91:5: note: in expansion of macro 'REP'
   91 |     REP(i, a.dp.size()){
      |     ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4684 KB Output is correct
2 Correct 15 ms 4764 KB Output is correct
3 Correct 4686 ms 6444 KB Output is correct
4 Correct 16 ms 4684 KB Output is correct
5 Correct 17 ms 4764 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 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 252 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 22 ms 332 KB Output is correct
5 Correct 22 ms 340 KB Output is correct
6 Correct 24 ms 344 KB Output is correct
7 Correct 22 ms 332 KB Output is correct
8 Correct 17 ms 336 KB Output is correct
9 Correct 21 ms 340 KB Output is correct
10 Correct 18 ms 348 KB Output is correct
11 Correct 10772 ms 1336 KB Output is correct
12 Correct 22 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 544 KB Output is correct
2 Correct 748 ms 532 KB Output is correct
3 Correct 768 ms 532 KB Output is correct
4 Correct 780 ms 536 KB Output is correct
5 Correct 759 ms 532 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 204 KB Output is correct
9 Correct 769 ms 560 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 105 ms 8652 KB Output is correct
2 Correct 113 ms 8652 KB Output is correct
3 Correct 105 ms 8652 KB Output is correct
4 Correct 9926 ms 9524 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 528 KB Output is correct
2 Correct 750 ms 580 KB Output is correct
3 Correct 770 ms 580 KB Output is correct
4 Correct 783 ms 548 KB Output is correct
5 Correct 763 ms 532 KB Output is correct
6 Correct 105 ms 8652 KB Output is correct
7 Correct 105 ms 8652 KB Output is correct
8 Correct 105 ms 8652 KB Output is correct
9 Correct 9901 ms 9380 KB Output is correct
10 Correct 15 ms 4684 KB Output is correct
11 Correct 16 ms 4764 KB Output is correct
12 Correct 7291 ms 6492 KB Output is correct
13 Correct 16 ms 4684 KB Output is correct
14 Correct 16 ms 4684 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 22 ms 344 KB Output is correct
19 Correct 22 ms 332 KB Output is correct
20 Correct 22 ms 348 KB Output is correct
21 Correct 22 ms 332 KB Output is correct
22 Correct 17 ms 340 KB Output is correct
23 Correct 21 ms 332 KB Output is correct
24 Correct 18 ms 340 KB Output is correct
25 Correct 10651 ms 1348 KB Output is correct
26 Correct 22 ms 332 KB Output is correct
27 Correct 773 ms 552 KB Output is correct
28 Execution timed out 20079 ms 15940 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 548 KB Output is correct
2 Correct 743 ms 460 KB Output is correct
3 Correct 770 ms 548 KB Output is correct
4 Correct 776 ms 536 KB Output is correct
5 Correct 762 ms 580 KB Output is correct
6 Correct 106 ms 8652 KB Output is correct
7 Correct 106 ms 8652 KB Output is correct
8 Correct 105 ms 8652 KB Output is correct
9 Correct 9995 ms 9412 KB Output is correct
10 Correct 15 ms 4684 KB Output is correct
11 Correct 16 ms 4764 KB Output is correct
12 Correct 4712 ms 6300 KB Output is correct
13 Correct 16 ms 4684 KB Output is correct
14 Correct 15 ms 4772 KB Output is correct
15 Correct 9515 ms 26120 KB Output is correct
16 Execution timed out 20087 ms 24140 KB Time limit exceeded
17 Halted 0 ms 0 KB -