結果
問題 | No.1211 円環はお断り |
ユーザー |
![]() |
提出日時 | 2020-08-30 14:14:59 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,258 ms / 2,000 ms |
コード長 | 1,646 bytes |
コンパイル時間 | 626 ms |
コンパイル使用メモリ | 79,940 KB |
実行使用メモリ | 21,376 KB |
最終ジャッジ日時 | 2024-11-23 16:12:54 |
合計ジャッジ時間 | 21,692 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#define llint long long#define inf 1e18#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define mod 1000000007using namespace std;typedef pair<llint, llint> P;llint n, k;llint a[300005], sum[300005];llint succ[100005][17];bool check(llint d){if(d > sum[n]) return false;llint r = -1;for(int i = 0; i < n; i++){while(r < i || sum[r]-sum[i] < d) r++;succ[i][0] = r-i;//lower_bound(sum, sum+3*n, sum[i] + d) - (sum+i);}for(int i = 1; i < 17; i++){for(int j = 0; j < n; j++){succ[j][i] = succ[j][i-1] + succ[(j+succ[j][i-1])%n][i-1];}}for(int i = 0; i < n; i++){llint v = i, s = 0;for(int j = 16; j >= 0; j--){if(k & (1<<j)){s += succ[v][j];if(s > n) goto end;v += succ[v][j], v %= n;}}return true;end:;}return false;}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;for(int i = 0; i < n; i++) cin >> a[i];for(int i = n; i < 3*n; i++) a[i] = a[i%n];llint s = 0;for(int i = 0; i < 3*n; i++){sum[i] = s;s += a[i];}llint ub = 2e14, lb = 0, mid;while(ub-lb>1){mid = (ub+lb)/2;if(check(mid)) lb = mid;else ub = mid;}cout << lb << endl;return 0;}