QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149631 | #6130. Plants vs. Zombies | pooty# | RE | 1ms | 19188kb | C++20 | 1.5kb | 2023-08-25 00:23:14 | 2023-08-25 00:23:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPL(i,j, n) for (int i = (j); i < (n); i++)
#define int long long
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int MAXX = 1e6;
int curman[MAXX*2];
vi toclear;
int solve() {
int n,m;cin>>n>>m;
if (m < n) return 0;
vi arr(n);
REP(i, n) {
cin>>arr[i];
}
int mx = 1e18;
int mn = 1e9;
for (auto x: arr) {
mn = min(x, mn);
}
while (mn < mx) {
int md = (mn + mx + 1)/2;
vi farr(n);
REP(i, n) {
farr[i] = md/arr[i];
if (md%arr[i] != 0) {
farr[i]++;
}
}
int needed = accumulate(farr.begin(), farr.end(), 0LL);
int defneed = needed;
REPL(i, 1, n) {
int v = min(farr[i], farr[i-1]);
farr[i-1] -= v;
farr[i] -= v;
if (farr[i-1] > 0) {
needed += farr[i-1];
}
}
needed += farr[n-1];
int gg = max(defneed, needed -1);
if (gg > m) {
mx = md - 1;
} else {
mn = md;
}
}
return mn;
}
signed main() {
memset(curman, 0, sizeof(curman));
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while (t--) {
cout<<solve()<<"\n";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 19188kb
input:
2 4 8 3 2 6 6 3 9 10 10 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #2:
score: -100
Runtime Error
input:
116 4 0 3 2 6 6 4 1 3 2 6 6 10 19 10 2 8 4 2 4 9 3 3 3 4 8 3 9 3 6 2 19 2 10 11 15 3 1 1 4 3 7 10 8 6 7 10 10 14 8 7 1 1 10 9 2 8 10 7 2 13 2 3 10 10 8 1 6 6 9 4 7 1 8 8 7 14 6 7 4 5 3 1 3 11 6 8 1 10 9 7 2 6 6 1 3 9 4 10 6 1 3 8 7 7 10 6 2 10 4 7 2 5 11 9 10 5 9 2 9 1 2 4 8 6 2 8 8 1 6 4 5 7 2 9 8 ...