QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#685562 | #9529. Farm Management | Godwang | WA | 1ms | 7768kb | C++23 | 6.3kb | 2024-10-28 20:08:29 | 2024-10-28 20:08:30 |
Judging History
answer
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#include<list>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define lowbit(x) ((x)&(-x))
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll fastpow(ll a, ll n, ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a) % mod; //% mod
a = (a * a) % mod; //% mod
n >>= 1;
}
return ans;
}
inline void write(__int128 x)
{
if (x > 9)
{
write(x / 10);
}
putchar(x % 10 + '0');
}
__int128 sqrt(__int128 m)
{
__int128 leftt = 0, rightt = ((__int128)1) << 51, ret = -1, mid;
while (leftt < rightt)
{
mid = (leftt + rightt) / 2;
if (mid * mid > m)
{
rightt = mid;
}
else
{
leftt = mid + 1;
ret = mid;
}
}
return ret;
}
const double eps = 1e-6;
int sgn(double x)
{
if(fabs(x)<eps)
{
return 0;
}
else return x<0?-1:1;
}
struct Point
{
double x,y;
Point()
{
}
Point(double x,double y):x(x),y(y)
{
}
Point operator + (Point B)
{
return Point(x+B.x,y+B.y);
}
Point operator - (Point B)
{
return Point(x-B.x,y-B.y);
}
bool operator == (Point B)
{
return sgn(x-B.x)==0&&sgn(y-B.y)==0;
}
bool operator < (Point B)
{
return sgn(x-B.x)<0||(sgn(x-B.x)==0&&sgn(y-B.y)<0);
}
};
typedef Point Vector;
double Cross(Vector A,Vector B)//叉积
{
return A.x*B.y-A.y*B.x;
}
double Distance(Point A,Point B)
{
return hypot(A.x-B.x,A.y-B.y);
}
int Convex_hull(Point *p,int n,Point *ch)
{
n=unique(p,p+n)-p;
sort(p,p+n);
int v=0;
for(int i=0;i<n;i++)
{
while (v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0)
{
v--;
}
ch[v++]=p[i];
}
int j=v;
for(int i=n-2;i>=0;i--)
{
while (v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1]))<=0)
{
v--;
}
ch[v++]=p[i];
}
if(n>1)
{
v--;
}
return v;
}
int kmp(string s, string p)
{
int ans = 0, lastt = -1;
int lenp = p.size();
vector<int > Next(lenp+3,0);
rep(i, 1, lenp - 1)
{
int j = Next[i];
while (j && p[j] != p[i])
{
j = Next[j];
}
if (p[j] == p[i])
{
Next[i + 1] = j + 1;
}
else
{
Next[i + 1] = 0;
}
}
int lens = s.size();
int j = 0;
rep(i, 0, lens - 1)
{
while (j && s[i] != p[j])
{
j = Next[j];
}
if (s[i] == p[j])
{
j++;
}
if (j == lenp)
{
ans++;
}
}
return ans;
}
int dir[4][2] =
{
{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 左右上下
// int dir[8][2]={
// {-1, 0}, {0, 1}, {1, 0}, {0, -1},{-1,-1},{-1,1},{1,-1},{1,1}
// };
#define endl '\n'//交互题请删除本行
const ll inf = 1000000000000000000ll;
const ll mod1 = 998244353ll, P1 = 131, mod2 = 1e9 + 7ll, P2 = 13331;
ll inverse(ll x)
{
return fastpow(x,mod1-2,mod1);
}
const int N = 1e5 + 10, M = 1e6 + 10;
///////////////////////////////////
int tt;
int n;
ll m;
ll shijianxiaxian;
ll leftt[N],rightt[N],w[N];
ll sumshang[N],sumxia[N],sumtime[N];
ll ans;
ll mintime;
struct node
{
ll w,l,r;
}st[N];
///////////////////////////////////
bool cmp(node x,node y)
{
return x.w<y.w;
}
void _()
{
ll zong=0;
rep(i,1,n)
{
zong+=leftt[i];
}
ans=max(ans,sumxia[1]+(m-zong)*w[n]);
}
///////////////////////////////////
void init()
{
}
///////////////////////////////////
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//交互题请删除本行
// freopen("ain.txt", "r", stdin); freopen("aout.txt", "w", stdout);
cin>>n>>m;
rep(i,1,n)
{
cin>>st[i].w>>st[i].l>>st[i].r;
mintime+=st[i].l;
}
sort(st+1,st+n+1,cmp);
rep(i,1,n)
{
leftt[i]=st[i].l;
rightt[i]=st[i].r;
w[i]=st[i].w;
}
per(i,1,n)
{
sumtime[i]=sumtime[i+1]+rightt[i]-leftt[i];
sumshang[i]=sumshang[i+1]+rightt[i]*w[i];
sumxia[i]=sumxia[i+1]+leftt[i]*w[i];
}
//
// cout<<sumxia[1]<<endl;
//add the last one
_();
// cout<<ans<<endl;
ll kezhipei=m-mintime;
rep(i,1,n)
{
ll temp=kezhipei+leftt[i];
if(sumtime[i+1]>temp)
{
if(sumtime[i+1]-kezhipei<leftt[i])
{
ll jiang=sumtime[i+1]-kezhipei;
ans=max(ans,sumxia[1]-sumxia[i]+(leftt[i]-jiang)*w[i]+sumshang[i+1]);
}
continue;
}
ll L=i+1,R=n+2;
ll man=n+2;
while (L<R)
{
ll mid=(L+R)>>1;
if(sumtime[mid]<=temp)
{
man=min(man,mid);
R=mid;
}
else
{
L=mid+1;
}
}
ll qiann=sumshang[man]+(temp-sumtime[man])*w[man-1];
qiann+=sumxia[1]-sumxia[man];
qiann-=leftt[i]*w[i];
ans=max(ans,qiann);
//
// cout<<i<<" "<<ans<<endl;
}
cout<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7672kb
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: 1ms
memory: 7768kb
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:
32281150
result:
wrong answer 1st lines differ - expected: '35204500', found: '32281150'