QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#683088 | #9529. Farm Management | wt_vic | WA | 0ms | 3852kb | C++14 | 8.0kb | 2024-10-27 18:43:24 | 2024-10-27 18:43:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solveK() {
ll n,m;
cin >> n >> m;
vector<ll>w(n),l(n),r(n),p(n);
ll s = 0;
for(int i = 0;i < n;i ++ ) {
cin >> w[i] >> l[i] >> r[i];
s += l[i];
}
iota(p.begin(),p.end(),0);
sort(p.begin(),p.end(),[&](int a,int b) {
return w[a] > w[b];
});
vector<ll>rs(n + 1),ls(n + 1),d(n + 1);
for(int i = 0;i < n;i ++ ) {
int id = p[i];
ls[i + 1] = ls[i] + w[id] * l[id];
rs[i + 1] = rs[i] + w[id] * r[id];
d[i + 1] = d[i] + (r[id] - l[id]);
}
ll t = m - s,ans = 0;
for(int i = 1;i <= n;i ++ ) {
int id = p[i - 1];
t += l[id];
int pos = upper_bound(d.begin() + 1,d.end(),t) - d.begin() - 1;
ll res = 0;
if(pos < i) {
int det = t - d[pos];// pos + 2 <= i - 1
res = rs[pos] + w[pos + 1] * det + (ls[n] - ls[i]) + (pos + 2 <= i - 1 ? (ls[i - 1] - ls[pos + 1]) : 0);
}else {
int det = t - d[i - 1];
res = rs[i - 1] + w[id] * det + (ls[n] - ls[i]);
}
ans = max(ans,res);
t -= l[id];
}
cout << ans << "\n";
}
const int N = 1e5 + 5;
struct Node
{
int l,r;
int x,len;
}tr[N << 2];
int a[N],b[N];
vector<int>p,d;
void pushup(int u) {
if(tr[u << 1].x == tr[u << 1].len)
tr[u].x = tr[u << 1].x + tr[u << 1 | 1].x;
else tr[u].x = tr[u << 1].x;
}
void build(int u,int l,int r) {
tr[u] = {l,r,0,r - l + 1};
if(l == r) {
if(a[l] == 0)tr[u].x = 1;
else tr[u].x = 0;
return;
}
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
pushup(u);
}
void modify(int u,int x,int c) {
if(tr[u].l == tr[u].r) {
if(c == 0)tr[u].x = 1;
else tr[u].x = 0;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)modify(u << 1,x,c);
else modify(u << 1 | 1,x,c);
pushup(u);
}
int query(int u,int l,int r) {
if(tr[u].l >= l and tr[u].r <= r) {
if(tr[u].x == tr[u].len)return -1;
else return tr[u].x + tr[u].l;
}
int mid = tr[u].l + tr[u].r >> 1;
int x = query(u << 1,l,r);
if(x == -1) {
return query(u << 1 | 1,l,r);
}else return x;
}
void solveJ() {
int n,m;
for(int i = 1;i <= n;i ++ ) {
cin >> a[i];b[i] = a[i];
}
int pre = 0;
p.push_back(0);
d.push_back(0);
vector<int>st(n + 1);
for(int i = 1;i <= m;i ++ ) {
int x,t;
cin >> x >> t;
int dis = x - pre;
pre = x;
p.push_back(t);
st[t] ++;
d.push_back(dis);
}
build(1,1,m);
ll sum = 0;
for(int i = 1;i <= n;i ++ ) {
if(!st[i])sum += a[i];
}
int k = 0;
ll ans = 0;
bool f = 0;
for(int i = 1;i <= m;i ++ ) {
int dis = d[i];
while(dis > 0) {
int pos = query(1,i,m);
if(pos == -1) {
if(sum >= dis) {
ans += dis;
sum -= dis;
dis = 0;
}else {
ans += sum;
dis -= sum;
sum = 0;
f = 1;break;
}
}else {
if(dis >= a[p[pos]]) {
ans += a[p[pos]];
dis -= a[p[pos]];
modify(1,pos,0);
a[p[pos]] = 0;
}else {
ans += dis;
a[p[pos]] -= dis;
dis = 0;
}
}
}
if(f == 1)break;
modify(1,i,1);
a[p[i]] = b[p[i]];
;
if(!--st[p[i]]) sum += a[p[i]];
}
ans += sum;
cout << ans << "\n";
}
typedef pair<int,int> pii;
vector<pii>G[101];
int link[101];
void solve() {
int l,r;
cin >> l >> r;
memset(link,-1,sizeof link);
int node = 2,tar = 2;//起点为1 终点为2
int mx = -1;
function<void(int,int,int)> dfs = [&](int l,int r,int k) -> void{
/*
100011 0 10100 -> 10100 ~ 11111
100011 1 11110 -> 00000 ~ 11110
1 0 100 -> 100 ~ 111
1 1 111 -> 000 ~ 111
~~~~~~~~~~~~~~~~~~~~
0 0001 -> 0001 ~ 1111
1 1110 -> 0000 ~ 1110
0 001 -> 001 ~ 111
1 111 -> 000 ~ 111 X
0 01 -> 01 ~ 11
1 11 -> 00 ~ 11 X
0 1 -> 1 ~ 1 X
1 1 -> 0 ~ 1 X
0 000 -> 000 ~ 111 X
1 110 -> 000 ~ 110
0 00 -> 00 ~ 11 X
1 10 -> 00 ~ 10
0 0 -> 0 1 X
1 0 -> 0 0 X
*/
int now = k;
int x = -1;
int t = 19;
if(l == r and (l == 0 || l == 1)) {
G[now].push_back({tar,l});
return;
}
while(!(r >> t & 1))t --;
if(l == r) {
for(int i = t;i;i -- ) {
G[now].push_back({++ node,(r >> i & 1)});
now = node;
}
G[now].push_back({tar,r & 1});
return;
}
for(int i = t;i >= 0;i -- ) {
if((r >> i & 1) != (l >> i & 1)) {
x = i;
break;
}else {
G[now].push_back({++ node,(r >> i & 1)});
now = node;
}
}
if(l == 0 and r == (1 << x + 1) - 1) {
// link 到 i -> i + 1 {0,1}的链
link[now] = x;
mx = max(mx,x);
return;
}
int s = l >> x << x;
if(x == 0) {
G[now].push_back({tar,1});
G[now].push_back({tar,0});
return;
}
// cout << l - s << ' ' << (1 << x) - 1 << endl;
// cout << 0 << ' ' << r - s - (1 << x) << endl;
G[now].push_back({node + 1,0});
G[now].push_back({node + 2,1});
int d = node;
node += 2;
dfs(l - s,(1 << x) - 1,d + 1);
int j = (__lg(r - s - (1 << x)));
now = d + 2;
while(x != j + 1) {
G[now].push_back({++ node,0});
now = node;
j ++;
}
//if(d == 7)cout << d + 2 << now << "\n";
dfs(0,r - s - (1 << x),now);
};
int f1 = -1,f2 = -1;
for(int i = 0;i < 20;i ++ ) {
if(l >> i & 1)f1 = i;
if(r >> i & 1)f2 = i;
}
int L = l;
for(int i = f1 + 1;;i ++ ) {
int R = (1 << i) - 1;
R = min(R,r);
dfs(L,R,1);
if(R >= r) {
break;
}
L = R + 1;
}
if(mx != -1) {
G[node + 1].push_back({tar,1});
G[node + 1].push_back({tar,0});
for(int i = 2;i <= mx;i ++ ) {
G[node + i].push_back({node + i - 1,1});
G[node + i].push_back({node + i - 1,0});
}
for(int i = 1;i <= node;i ++ ) {
int x = link[i];
if(x == -1)continue;
// cout << i << ' ' << x << '\n';
if(x == 0) {
G[i].push_back({tar,1});
G[i].push_back({tar,0});
}
else {
G[i].push_back({node + x,1});
G[i].push_back({node + x,0});
}
}
}
/*cout << node + mx << "\n";
for(int i = 1;i <= node + mx;i ++ ) {
cout << G[i].size() << " ";
for(auto [v,w] : G[i]) {
cout << v << ' ' << w << ' ';
}
cout << "\n";
}*/
for(int i = 1;i <= node + mx;i ++ ) {
for(auto [v,w] : G[i]) {
cout << i << ' ' << v << ' ' << w << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin >> T;
while(T -- ) {
solveK();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3852kb
input:
5 17 2 3 4 6 1 5 8 2 4 4 3 3 7 5 5
output:
109
result:
ok single line: '109'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3816kb
input:
12 62 503792 9 10 607358 1 3 600501 10 10 33249 4 4 774438 6 6 197692 3 6 495807 8 8 790225 5 9 77272 3 8 494819 4 9 894779 3 9 306279 5 6
output:
34251689
result:
wrong answer 1st lines differ - expected: '35204500', found: '34251689'