Submission #1004441
Source Code Expand
#include <bits/stdc++.h> #define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ ) #define REP(i,n) FOR(i,0,n) #define YYS(x,arr) for(auto& x:arr) #define ALL(x) (x).begin(),(x).end() #define SORT(x) sort( (x).begin(),(x).end() ) #define REVERSE(x) reverse( (x).begin(),(x).end() ) #define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() ) #define PW(x) (1LL<<(x)) #define SZ(x) ((ll)(x).size()) #define SHOW(x) cout << #x << " = " << x << endl #define pb emplace_back #define fi first #define se second using namespace std; typedef long double ld; typedef long long int ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<bool> vb; typedef vector<ld> vd; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<vpl> gr; typedef vector<vl> ml; typedef vector<vd> md; typedef vector<vi> mi; const ll INF = (ll)1e9 + 10; const ll INFLL = (ll)1e18 + 10; const ld EPS = 1e-12; const ll MOD = 1e9+7; template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); } template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); } template<class T> inline T sq( T a ){ return a * a; } ll in(){ ll x; scanf( "%lld" , &x ); return x; } char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; } // head ll dp[2010][2010]; ll comb( ll a , ll b ){ if( b < 0 or b > a ){ return 0; } if( b == 0 or b == a ){ return 1; } if( a >= 2010 ){ if( b == 1 || b == a - 1 ){ return min( INF , a ); } else if( b == 2 || b == a - 2 ){ return min( INF , a * ( a - 1 ) / 2 ); } else if( b == 3 ){ return INF; } } if( dp[a][b] != 0 ){ return dp[a][b]; } ll res = comb( a - 1 , b ) + comb( a - 1 , b - 1 ); return dp[a][b] = min( res , INF ); } int n, m; pi calc( vi a , vi b ){ assert( a < b ); int x = ( b[1] - a[1] ) / a[0]; FOR( i , 1 , m ){ ll cur = a[i]; FOR( j , 1 , i+1 ){ cur += a[i-j] * comb( x + j - 1 , j ); chmin( cur , INF ); } if( cur > b[i] ){ return make_pair( x , false ); } if( cur < b[i] ){ return make_pair( x + 1 , false ); } } return make_pair( x , true ); } mi a; int main(){ n = in(); m = in(); a = mi( n , vi( m ) ); REP( i , n ){ REP( j , m ){ a[i][j] = in(); } } if( m == 1 ){ REP( i , n-1 ){ if( a[i][0] >= a[i+1][0] ){ puts( "-1" ); return 0; } } puts( "0" ); return 0; } REP( i , n-1 ){ if( a[i][0] > a[i+1][0] ){ puts( "-1" ); return 0; } } ll cur = 0; ll ans = 0; REP( i , n-1 ){ if( a[i][0] == a[i+1][0] ){ if( a[i][1] < a[i+1][1] ){ pi res = calc( a[i] , a[i+1] ); cur = cur - res.fi + 1; } else if( a[i][1] > a[i+1][1] ){ pi res = calc( a[i+1] , a[i] ); if( res.se ){ cur = cur + res.fi + 1; } else { cur = cur + res.fi; } } else { if( a[i] >= a[i+1] ){ cur++; } } } else { cur = 0; } chmax( cur , 0LL ); ans += cur; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Takahashi the Magician |
User | joisino |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 3281 Byte |
Status | AC |
Exec Time | 418 ms |
Memory | 8192 KB |
Compile Error
./Main.cpp: In function ‘ll in()’: ./Main.cpp:44:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] ll in(){ ll x; scanf( "%lld" , &x ); return x; } ^ ./Main.cpp: In function ‘std::string stin()’: ./Main.cpp:45:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; } ^
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 800 / 800 | 200 / 200 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 | sample_1.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
hack_1.txt | AC | 3 ms | 256 KB |
hack_2.txt | AC | 3 ms | 256 KB |
hack_3.txt | AC | 3 ms | 256 KB |
hack_4.txt | AC | 3 ms | 256 KB |
hack_5.txt | AC | 3 ms | 256 KB |
sample_1.txt | AC | 3 ms | 256 KB |
sample_2.txt | AC | 3 ms | 256 KB |
sample_3.txt | AC | 3 ms | 256 KB |
subtask_1_1.txt | AC | 3 ms | 256 KB |
subtask_1_10.txt | AC | 3 ms | 256 KB |
subtask_1_11.txt | AC | 112 ms | 4224 KB |
subtask_1_12.txt | AC | 3 ms | 256 KB |
subtask_1_13.txt | AC | 3 ms | 256 KB |
subtask_1_14.txt | AC | 3 ms | 512 KB |
subtask_1_15.txt | AC | 115 ms | 4224 KB |
subtask_1_16.txt | AC | 119 ms | 4224 KB |
subtask_1_17.txt | AC | 119 ms | 4224 KB |
subtask_1_18.txt | AC | 116 ms | 4224 KB |
subtask_1_19.txt | AC | 3 ms | 512 KB |
subtask_1_2.txt | AC | 3 ms | 256 KB |
subtask_1_20.txt | AC | 3 ms | 256 KB |
subtask_1_3.txt | AC | 3 ms | 256 KB |
subtask_1_4.txt | AC | 3 ms | 384 KB |
subtask_1_5.txt | AC | 3 ms | 384 KB |
subtask_1_6.txt | AC | 4 ms | 384 KB |
subtask_1_7.txt | AC | 4 ms | 384 KB |
subtask_1_8.txt | AC | 114 ms | 4224 KB |
subtask_1_9.txt | AC | 42 ms | 2176 KB |
subtask_2_1.txt | AC | 10 ms | 640 KB |
subtask_2_10.txt | AC | 16 ms | 896 KB |
subtask_2_11.txt | AC | 82 ms | 4224 KB |
subtask_2_12.txt | AC | 82 ms | 4224 KB |
subtask_2_13.txt | AC | 82 ms | 4224 KB |
subtask_2_14.txt | AC | 83 ms | 4224 KB |
subtask_2_15.txt | AC | 3 ms | 256 KB |
subtask_2_16.txt | AC | 81 ms | 4224 KB |
subtask_2_17.txt | AC | 81 ms | 4224 KB |
subtask_2_18.txt | AC | 83 ms | 4480 KB |
subtask_2_19.txt | AC | 3 ms | 256 KB |
subtask_2_2.txt | AC | 79 ms | 4224 KB |
subtask_2_20.txt | AC | 3 ms | 256 KB |
subtask_2_21.txt | AC | 3 ms | 256 KB |
subtask_2_22.txt | AC | 3 ms | 256 KB |
subtask_2_23.txt | AC | 3 ms | 256 KB |
subtask_2_24.txt | AC | 3 ms | 256 KB |
subtask_2_25.txt | AC | 3 ms | 256 KB |
subtask_2_26.txt | AC | 3 ms | 256 KB |
subtask_2_27.txt | AC | 3 ms | 256 KB |
subtask_2_3.txt | AC | 79 ms | 4224 KB |
subtask_2_4.txt | AC | 41 ms | 2176 KB |
subtask_2_5.txt | AC | 82 ms | 4224 KB |
subtask_2_6.txt | AC | 83 ms | 4480 KB |
subtask_2_7.txt | AC | 33 ms | 1792 KB |
subtask_2_8.txt | AC | 7 ms | 512 KB |
subtask_2_9.txt | AC | 20 ms | 1152 KB |
subtask_3_1.txt | AC | 3 ms | 384 KB |
subtask_3_10.txt | AC | 119 ms | 4224 KB |
subtask_3_11.txt | AC | 119 ms | 4224 KB |
subtask_3_12.txt | AC | 119 ms | 4224 KB |
subtask_3_13.txt | AC | 3 ms | 256 KB |
subtask_3_14.txt | AC | 3 ms | 256 KB |
subtask_3_2.txt | AC | 4 ms | 384 KB |
subtask_3_3.txt | AC | 120 ms | 4224 KB |
subtask_3_4.txt | AC | 121 ms | 4224 KB |
subtask_3_5.txt | AC | 120 ms | 4224 KB |
subtask_3_6.txt | AC | 120 ms | 4224 KB |
subtask_3_7.txt | AC | 102 ms | 4352 KB |
subtask_3_8.txt | AC | 418 ms | 8192 KB |
subtask_3_9.txt | AC | 120 ms | 4224 KB |