Submission #00167
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <bits/stdc++.h> using namespace std; #define __ <<" "<< #define ___ <<" " #define bash push_back #define ALL(x) x.begin(),x.end() // #define int long long struct IoSetup { IoSetup() { cin.tie(0); ios::sync_with_stdio( false ); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } }IoSetup; using Int = __int128_t; using ll = long long ; using pii = pair< int , int >; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr int SMOD = 1000000007; constexpr int NMOD = 998244353; constexpr int dx[]={1,0,-1,0,1,1,-1,-1}; constexpr int dy[]={0,-1,0,1,-1,1,-1,1}; inline bool inside( int x, int y, int w, int h){ return (x>=0 && y>=0 && x<w && y<h);} template < class T> bool chmax(T &a, const T&b){ if (a<b) return (a=b,1); return 0;} template < class T> bool chmin(T &a, const T&b){ if (b<a) return (a=b,1); return 0;} int h, n; int mem[11111][40]; int mas[11111][10]; int mask[11111]; int dfs( int i, int bit) { if (mask[i] & bit) return -INF; if (~mem[i][bit]) return mem[i][bit]; if (i == h - 1) return 0; mem[i][bit] = dfs(i+1, 0); if (!((bit | mask[i]) & 3)) chmax(mem[i][bit], dfs(i+1, 3) + 1); if (!((bit | mask[i]) & 6)) chmax(mem[i][bit], dfs(i+1, 6) + 1); if (!((bit | mask[i]) & 12)) chmax(mem[i][bit], dfs(i+1, 12) + 1); if (!((bit | mask[i]) & 15)) chmax(mem[i][bit], dfs(i+1, 15) + 2); return mem[i][bit]; } signed main() { cin >> h >> n; for ( int i = 0; i < n; i++) { int x, y; cin >> x >> y; mas[y][x] = 1; } for ( int i = 0; i < h; i++) { mask[i] = mas[i][0] + mas[i][1] * 2 + mas[i][2] * 4 + mas[i][3] * 8; } memset (mem, -1, sizeof (mem)); cout << dfs(0, 0) << endl; return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0007 - 積み荷の配置 |
ユーザー名 | 社会主義共和国連邦 |
投稿日時 | 2020-08-25 17:45:38 |
言語 | C++14 |
状態 | Accepted |
得点 | 11 |
ソースコード長 | 1844 Byte |
最大実行時間 | 38 ms |
最大メモリ使用量 | 3184 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 11 / 11 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
in1.txt | AC | 23 ms | 2268 KB |
1
|
in2.txt | AC | 21 ms | 2168 KB |
1
|
in3.txt | AC | 25 ms | 2284 KB |
1
|
in4.txt | AC | 21 ms | 2436 KB |
1
|
in5.txt | AC | 26 ms | 2436 KB |
1
|
in6.txt | AC | 27 ms | 2312 KB |
1
|
in7.txt | AC | 24 ms | 2444 KB |
1
|
in8.txt | AC | 28 ms | 2324 KB |
1
|
in9.txt | AC | 26 ms | 2456 KB |
1
|
in10.txt | AC | 27 ms | 2404 KB |
1
|
in11.txt | AC | 21 ms | 2204 KB |
1
|
in12.txt | AC | 21 ms | 2260 KB |
1
|
in13.txt | AC | 25 ms | 2188 KB |
1
|
in14.txt | AC | 27 ms | 3004 KB |
1
|
in15.txt | AC | 24 ms | 3012 KB |
1
|
in16.txt | AC | 27 ms | 3136 KB |
1
|
in17.txt | AC | 25 ms | 3144 KB |
1
|
in18.txt | AC | 27 ms | 2248 KB |
1
|
in19.txt | AC | 19 ms | 3060 KB |
1
|
in20.txt | AC | 38 ms | 2296 KB |
1
|
in21.txt | AC | 19 ms | 3116 KB |
1
|
in22.txt | AC | 24 ms | 3128 KB |
1
|
in23.txt | AC | 26 ms | 3132 KB |
1
|
in24.txt | AC | 21 ms | 3136 KB |
1
|
in25.txt | AC | 27 ms | 2244 KB |
1
|
in26.txt | AC | 19 ms | 2124 KB |
1
|
in27.txt | AC | 23 ms | 2768 KB |
1
|
in28.txt | AC | 22 ms | 3172 KB |
1
|
in29.txt | AC | 27 ms | 3180 KB |
1
|
in30.txt | AC | 29 ms | 3184 KB |
1
|
in31.txt | AC | 29 ms | 2428 KB |
1
|
in32.txt | AC | 24 ms | 2428 KB |
1
|