oj.uz

Submission #321120

# Submission time Handle Problem Language Result Execution time Memory
321120 2020-11-11T04:28:38 Z teehandsome Bitaro the Brave (JOI19_ho_t1) C++11
50 / 100
 482 ms 274432 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {for(auto e:x) cerr<<e<<",";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

int m,n;
char a[3002][3002];
int dp[3002][3002][4][3]; //i,j,fromdir,char
// 0=up,1=right,2=down,3=left
int dm[4]={-1,0,1,0}; int dn[4]={0,1,0,-1};
map<char,int> hsh;

int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    hsh['J']=0; hsh['O']=1; hsh['I']=2;
    cin>>m>>n;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            for(int k=0;k<3;k++) {
                dp[i][j][3][k]=(hsh[a[i][j]]==k)+dp[i][j-1][3][k];
            }
        }
        for(int j=n;j>=1;j--) {
            for(int k=0;k<3;k++) {
                dp[i][j][1][k]=(hsh[a[i][j]]==k)+dp[i][j+1][1][k];
            }
        }
    }
    for(int j=1;j<=n;j++) {
        for(int i=1;i<=m;i++) {
            for(int k=0;k<3;k++) {
                dp[i][j][0][k]=(hsh[a[i][j]]==k)+dp[i-1][j][0][k];
            }
        }
        for(int i=m;i>=1;i--) {
            for(int k=0;k<3;k++) {
                dp[i][j][2][k]=(hsh[a[i][j]]==k)+dp[i+1][j][2][k];
            }
        }
    }
//    for(int k=0;k<3;k++) {
//        for(int i=1;i<=m;i++) {
//            for(int j=1;j<=n;j++) {
//                cout<<dp[i][j][1][k]<<' ';
//            }
//            cout<<endl;
//        }
//        cout<<"======="<<endl;
//    }
    ll ans=0;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            if(a[i][j]!='J') continue;
//            int horO=dp[i][j-1][3][hsh['O']]+dp[i][j+1][1][hsh['O']];
//            //int horI=dp[i][j-1][3][hsh['I']]+dp[i][j+1][1][hsh['I']];
//            //int verO=dp[i-1][j][0][hsh['O']]+dp[i+1][j][2][hsh['O']];
//            int verI=dp[i-1][j][0][hsh['I']]+dp[i+1][j][2][hsh['I']];
//            ans+=1LL*(horO*verI)+1LL*horI*verO;
            int horO=dp[i][j+1][1][hsh['O']];
            int verI=dp[i+1][j][2][hsh['I']];
            ans+=1LL*horO*verI;
        }
    }
    cout<<ans<<endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1536 KB Output is correct
7 Correct 2 ms 1388 KB Output is correct
8 Correct 2 ms 1516 KB Output is correct
9 Correct 2 ms 1516 KB Output is correct
10 Correct 2 ms 1388 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 2 ms 1516 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1536 KB Output is correct
7 Correct 2 ms 1388 KB Output is correct
8 Correct 2 ms 1516 KB Output is correct
9 Correct 2 ms 1516 KB Output is correct
10 Correct 2 ms 1388 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 2 ms 1516 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct
14 Correct 34 ms 13164 KB Output is correct
15 Correct 3 ms 3564 KB Output is correct
16 Correct 20 ms 8428 KB Output is correct
17 Correct 1 ms 620 KB Output is correct
18 Correct 40 ms 15972 KB Output is correct
19 Correct 36 ms 15588 KB Output is correct
20 Correct 31 ms 15596 KB Output is correct
21 Correct 41 ms 16108 KB Output is correct
22 Correct 34 ms 15460 KB Output is correct
23 Correct 32 ms 15596 KB Output is correct
24 Correct 43 ms 15980 KB Output is correct
25 Correct 34 ms 15468 KB Output is correct
26 Correct 32 ms 15596 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1536 KB Output is correct
7 Correct 2 ms 1388 KB Output is correct
8 Correct 2 ms 1516 KB Output is correct
9 Correct 2 ms 1516 KB Output is correct
10 Correct 2 ms 1388 KB Output is correct
11 Correct 2 ms 1516 KB Output is correct
12 Correct 2 ms 1516 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct
14 Correct 34 ms 13164 KB Output is correct
15 Correct 3 ms 3564 KB Output is correct
16 Correct 20 ms 8428 KB Output is correct
17 Correct 1 ms 620 KB Output is correct
18 Correct 40 ms 15972 KB Output is correct
19 Correct 36 ms 15588 KB Output is correct
20 Correct 31 ms 15596 KB Output is correct
21 Correct 41 ms 16108 KB Output is correct
22 Correct 34 ms 15460 KB Output is correct
23 Correct 32 ms 15596 KB Output is correct
24 Correct 43 ms 15980 KB Output is correct
25 Correct 34 ms 15468 KB Output is correct
26 Correct 32 ms 15596 KB Output is correct
27 Runtime error 482 ms 274432 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Halted 0 ms 0 KB -