QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #703956 | #112. Bulldozer | TheZone | 100 ✓ | 795ms | 54080kb | C++20 | 66.9kb | 2024-11-02 18:58:09 | 2024-11-02 18:58:10 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}/*#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2005;
int n,P[N],Q[N],tot,ans;
struct node {int x,y,w;} a[N];
bool cmpy(node &x,node &y) {return x.y==y.y?x.x<y.x:x.y>y.y;}
struct slp {int i,j,dx,dy;} b[N*N];
slp get_slope(int i,int j) { //yi>yj, xi>xj
slp b; b.i=i, b.j=j;
b.dy=a[i].y-a[j].y, b.dx=a[i].x-a[j].x;
return b;
}
bool cmps(slp &a,slp &b) {
return a.dy*b.dx<b.dy*a.dx;
}
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
bool eq(slp &a,slp &b) {
return a.dy*b.dx==b.dy*a.dx;
}
namespace SegT {
struct node {
int l,r,s,c;
node(int a=0) {s=a,l=r=c=max(a,0ll);}
};
node operator + (const node &a,const node &b) {
node c;
c.l=max(a.l,a.s+b.l);
c.r=max(b.r,b.s+a.r);
c.s=a.s+b.s;
c.c=max(max(a.c,b.c),a.r+b.l);
return c;
}
int ls[N<<1],rs[N<<1],tot=1; node s[N<<1];
void init() {
rep(i,1,tot) ls[i]=rs[i]=0, s[i]=node(0);
tot=1;
}
void build(int p,int l,int r) {
if(l==r) {s[p]=node(a[l].w); return;} int mid=l+r>>1;
build(ls[p]=++tot,l,mid), build(rs[p]=++tot,mid+1,r);
s[p]=s[ls[p]]+s[rs[p]];
}
void mdf(int p,int l,int r,int x,int y) {
if(l==r) {s[p]=node(y); return;} int mid=l+r>>1;
if(x<=mid) mdf(ls[p],l,mid,x,y); else mdf(rs[p],mid+1,r,x,y);
s[p]=s[ls[p]]+s[rs[p]];
}
int qry() {return s[1].c;}
}
void work() {
sort(a+1,a+n+1,cmpy); tot=0;
rep(i,1,n) rep(j,i+1,n) if(a[i].y>a[j].y&&a[i].x>a[j].x) b[++tot]=get_slope(i,j);
sort(b+1,b+tot+1,cmps);
SegT::init(); SegT::build(1,1,n);
rep(i,1,n) P[i]=Q[i]=i;
rep(i,1,tot) {
int p=i; vi e;
for(;i<=tot&&eq(b[p],b[i]);i++) {
if(Q[b[i].i]+1==Q[b[i].j]) {
e.eb(Q[b[i].i]);
}
} i--;
sort(e.begin(),e.end()); int sz=e.size();
chmax(ans,SegT::qry());
rep(j,0,sz-1) {
int k=j+1;
for(;k<sz&&e[k]==e[k-1]+1;k++); k--;
reverse(P+e[j],P+e[k]+2);
rep(x,e[j],e[k]+1) Q[P[x]]=x;
rep(x,e[j],e[k]+1) SegT::mdf(1,1,n,x,a[P[x]].w);
j=k;
}
}
}
void wory() {
int sum=0; sort(a+1,a+n+1,cmpy);
rep(i,1,n) chmax(ans,sum), sum=max(sum,0ll)+a[i].w;
chmax(ans,sum);
}
signed main() {
n=read();
rep(i,1,n) a[i].x=read(), a[i].y=read(), a[i].w=read();
work();
rep(i,1,n) a[i].x=-a[i].x;
work();
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
rep(i,1,n) swap(a[i].x,a[i].y);
wory();
rep(i,1,n) a[i].x=-a[i].x;
wory();
printf("%lld\n",ans);
return 0;
}v*/
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 3812kb
input:
100 547397735 0 -701876985 -994704489 0 -137482041 657756917 0 134137206 902929348 0 848664068 -942595218 0 905496420 -885718358 0 -183102425 -133322590 0 -765735957 40517489 0 137314145 -651698207 0 -755087111 -995622477 0 -437346891 905467861 0 -331241604 119881570 0 -555661137 -489890101 0 554937...
output:
3177735978
result:
ok single line: '3177735978'
Test #2:
score: 5
Accepted
time: 0ms
memory: 3880kb
input:
100 -261161481 0 -914392661 -666405901 0 -41566748 66756925 0 -998443149 952300068 0 573223358 309115993 0 -71109795 -437248002 0 -998530659 8869283 0 -747615449 49181126 0 438208683 581940102 0 716960639 77140827 0 -652930885 133126337 0 -222491793 867541743 0 390837222 167016881 0 -843021041 88598...
output:
4233982289
result:
ok single line: '4233982289'
Test #3:
score: 5
Accepted
time: 0ms
memory: 4148kb
input:
100 -222857036 0 974268066 -963708956 0 571111453 429775825 0 -488478252 -890405877 0 644217358 -145476249 0 165475563 29568362 0 -871157181 -590835003 0 -367690261 -949688033 0 862094564 -829133448 0 101313815 927649348 0 146819177 750589423 0 -857789865 986972806 0 -890509036 -345137050 0 -9560614...
output:
7862036314
result:
ok single line: '7862036314'
Test #4:
score: 5
Accepted
time: 0ms
memory: 3948kb
input:
100 -765834815 0 793761317 -590714711 0 877069467 875088436 0 -731140189 585062563 0 881661413 -43312535 0 178316122 -332128714 0 -301531685 105303357 0 -34868508 -530964546 0 586283855 -239824340 0 -697091034 939764764 0 -594915278 -792023779 0 697168838 -375624278 0 -609724856 24743017 0 -93058205...
output:
8526209158
result:
ok single line: '8526209158'
Test #5:
score: 5
Accepted
time: 0ms
memory: 3856kb
input:
100 -636880431 0 465934512 903773040 0 781918212 531633762 0 -668342878 124109692 0 -506553188 -291869987 0 -200916555 -647982335 0 -507011413 -933154753 0 -736194510 -501962655 0 103499621 454996768 0 -124979750 549671906 0 752281199 -292851807 0 -841066828 -146499552 0 -257697933 -975417825 0 -932...
output:
2625361444
result:
ok single line: '2625361444'
Test #6:
score: 5
Accepted
time: 0ms
memory: 3948kb
input:
100 -857394336 0 -944755079 -780006622 0 -139547826 -2560270 0 349126587 282599103 0 -11738099 -460221770 0 625520397 36526360 0 -996812076 -811403082 0 -125116484 380912231 0 983338070 -416153287 0 642400465 336292294 0 -651556660 -709948524 0 -990304229 823950984 0 -930807543 -895326122 0 47665213...
output:
3874129803
result:
ok single line: '3874129803'
Test #7:
score: 5
Accepted
time: 0ms
memory: 4144kb
input:
100 -975151282 0 -465136862 422840744 0 -605491521 -442164576 0 264906611 -547427714 0 -91634247 -431211607 0 120363028 -381891858 0 127165539 -954954108 0 -819088685 138832911 0 -448464992 -766994308 0 -729401566 436164370 0 961590254 -449775864 0 -247831509 -666671795 0 -842063887 -923743845 0 173...
output:
4847418387
result:
ok single line: '4847418387'
Test #8:
score: 5
Accepted
time: 0ms
memory: 4116kb
input:
100 -669822387 0 922925305 -883818451 0 8479702 98172896 0 46045113 936068983 0 -503493338 -430857057 0 481009228 -323595794 0 -776889225 321116637 0 68975670 282010402 0 168401391 -584979742 0 -846678475 -885465473 0 -12475048 -997014156 0 -663885649 -107523102 0 -624884016 153462146 0 508478755 -8...
output:
2455488903
result:
ok single line: '2455488903'
Test #9:
score: 5
Accepted
time: 0ms
memory: 5892kb
input:
100 813401424 0 -862325176 -421905957 0 734638464 666910031 0 -842119169 -833302447 0 -111841505 720440241 0 772103976 400327483 0 -148258200 -435748418 0 906697520 630665390 0 986798888 -45117776 0 894199888 747899578 0 599624948 34177986 0 617453134 -985626489 0 -29101360 -46259591 0 364442775 851...
output:
6550560680
result:
ok single line: '6550560680'
Test #10:
score: 5
Accepted
time: 0ms
memory: 4140kb
input:
100 -925110578 0 230631768 -430445107 0 169066762 -974931672 0 -480757607 -863283656 0 380412476 378972090 0 -402256816 -496070525 0 241369732 -5219166 0 -593344355 -687047875 0 -787363637 -784209470 0 -344936103 592586642 0 -932899477 783917014 0 262250096 -932557920 0 374017595 945116339 0 -258993...
output:
4278493522
result:
ok single line: '4278493522'
Test #11:
score: 5
Accepted
time: 0ms
memory: 3952kb
input:
1 0 0 -1
output:
0
result:
ok single line: '0'
Test #12:
score: 5
Accepted
time: 0ms
memory: 3824kb
input:
1 0 0 1
output:
1
result:
ok single line: '1'
Test #13:
score: 5
Accepted
time: 0ms
memory: 4140kb
input:
2 0 0 1 1 0 -1
output:
1
result:
ok single line: '1'
Test #14:
score: 5
Accepted
time: 0ms
memory: 3836kb
input:
2 0 0 1 1 0 1
output:
2
result:
ok single line: '2'
Test #15:
score: 5
Accepted
time: 0ms
memory: 3876kb
input:
3 0 0 2 1 0 -1 2 0 2
output:
3
result:
ok single line: '3'
Subtask #2:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 2ms
memory: 3904kb
input:
100 -24309550 482269965 -297648951 253448360 -441723643 -920713212 324597788 390083514 -865804754 713394653 -881475679 678850273 -445282104 369972896 691296843 69042891 -867513631 -239602542 -391732493 330791482 17449017 279658315 890578483 565738698 625283527 15481214 530839875 592822547 33796172 4...
output:
8062662362
result:
ok single line: '8062662362'
Test #17:
score: 20
Accepted
time: 2ms
memory: 4228kb
input:
100 -257587011 400852223 -220309345 -875500067 -86782621 326270594 -414287853 -977479920 -984533791 -635666918 -708630100 326066280 -615040019 -993541890 -685301992 -760310577 221302942 45160524 -990846996 351043755 -648825880 -918729931 -379977547 911808427 252530998 107120801 -919405596 507878869 ...
output:
7374350612
result:
ok single line: '7374350612'
Test #18:
score: 20
Accepted
time: 2ms
memory: 4024kb
input:
100 -234721699 646933168 -338655575 -806569531 -71216264 -872209889 740102166 -655865625 80137029 -619042650 86451086 919481887 -613310459 862325871 299940063 -486792319 385052870 -459562867 -877904368 -297131478 447851188 199060395 -82554072 -131371354 -952281361 -710915129 307615240 -507291693 907...
output:
6210932418
result:
ok single line: '6210932418'
Test #19:
score: 20
Accepted
time: 2ms
memory: 6072kb
input:
100 -573155230 -21482599 137188437 -858318223 -627279123 74329590 -17310327 -177777278 788416416 -670979585 820505465 -787614633 562566093 273531226 733397305 -64307790 599053244 -297009699 817165433 -369316382 924081906 720802586 596624938 351428871 115928798 523348194 -586662700 -885459046 -895204...
output:
8054120128
result:
ok single line: '8054120128'
Test #20:
score: 20
Accepted
time: 2ms
memory: 3932kb
input:
100 701468719 174754273 994891446 508373256 -732987695 648967734 369948378 -700859918 834543102 -862822283 -588546632 -394089051 -880849099 -911153118 -293420654 861677968 917107626 824561386 -359587638 -857777409 -913592764 -135640113 -867460034 933004325 -971454790 -711909514 -274071917 953354587 ...
output:
11634325865
result:
ok single line: '11634325865'
Test #21:
score: 20
Accepted
time: 2ms
memory: 3968kb
input:
100 -406079738 55160150 -920565361 725055282 878590579 -800311783 -670162535 901392505 240442550 179342318 -384964487 -877645265 592925162 -971845016 -313276130 -659126723 30771322 771426239 -749159311 433142945 -927853693 -676435064 -378708256 -634922247 -486642852 229623957 530273029 -269137808 57...
output:
5685526749
result:
ok single line: '5685526749'
Test #22:
score: 20
Accepted
time: 2ms
memory: 4024kb
input:
100 -689190423 220983861 913342760 -807787476 31872295 443021122 -815582432 -456178077 894438019 326141220 -885526038 -427240265 390679145 408965343 -859292305 -928486438 685567377 248489199 -45211459 -700556605 17089679 -28845394 -9042916 -609052379 -469176499 481816321 -964805208 -918568308 448434...
output:
5621356954
result:
ok single line: '5621356954'
Test #23:
score: 20
Accepted
time: 2ms
memory: 4004kb
input:
100 187164857 900233795 990568533 -125876794 892832559 -940816798 -321878196 394069566 -244480066 -670273914 544753218 376169540 910151452 -861989228 -628283308 352749124 -819374074 741277319 -344455996 -217000212 -944332393 93217857 -174981978 -180151861 94543655 256400293 -888939691 782508726 -969...
output:
5036576367
result:
ok single line: '5036576367'
Test #24:
score: 20
Accepted
time: 2ms
memory: 3940kb
input:
100 531363827 -977931429 -76627691 566440726 -235229527 337777732 89516229 -489823739 -691867132 907305820 -945880242 -285222604 -183193668 -54409760 574440897 985173840 -947464549 358402992 38982981 -262700773 -810245538 193675330 -701123831 627792386 738870352 -634028033 -781105055 187273959 -5919...
output:
6460320517
result:
ok single line: '6460320517'
Test #25:
score: 20
Accepted
time: 2ms
memory: 3964kb
input:
100 -353174997 -351995784 -310183082 654678384 947350572 758744270 37126054 247124163 -388016820 282286988 -992350460 -723589942 531405766 108105766 52078769 -344987066 557794460 305053304 787276939 -576929156 212556717 34490507 -937159146 -794206787 368163585 -217235651 952032589 11623915 -65802595...
output:
8695946466
result:
ok single line: '8695946466'
Test #26:
score: 20
Accepted
time: 0ms
memory: 4144kb
input:
1 0 0 -1
output:
0
result:
ok single line: '0'
Test #27:
score: 20
Accepted
time: 0ms
memory: 5992kb
input:
1 0 0 1
output:
1
result:
ok single line: '1'
Test #28:
score: 20
Accepted
time: 0ms
memory: 3880kb
input:
2 0 0 1 0 1 -1
output:
1
result:
ok single line: '1'
Test #29:
score: 20
Accepted
time: 0ms
memory: 3944kb
input:
2 0 0 1 0 1 1
output:
2
result:
ok single line: '2'
Test #30:
score: 20
Accepted
time: 0ms
memory: 3916kb
input:
3 -196970608 -259062089 -315946900 -880312834 -824169703 695651137 -952951255 -453975245 -456334228
output:
695651137
result:
ok single line: '695651137'
Test #31:
score: 20
Accepted
time: 0ms
memory: 3888kb
input:
3 -904399232 197805285 -409227852 252002501 -603959820 -265360818 -584036233 955522285 -606118177
output:
0
result:
ok single line: '0'
Test #32:
score: 20
Accepted
time: 0ms
memory: 4148kb
input:
3 819901047 -930259703 -717371546 2759216 -889603050 232484320 468055317 -559162010 -804576960
output:
232484320
result:
ok single line: '232484320'
Test #33:
score: 20
Accepted
time: 0ms
memory: 3864kb
input:
4 -567458435 413660811 672407797 -52833185 -976745057 -137512537 -29340005 53972841 544308705 258569846 423384165 -271529583
output:
1216716502
result:
ok single line: '1216716502'
Test #34:
score: 20
Accepted
time: 0ms
memory: 3940kb
input:
4 518389369 280627664 -140579924 180993080 505035811 -618512465 262205753 -850582688 287042495 -979026791 443616387 467523162
output:
754565657
result:
ok single line: '754565657'
Test #35:
score: 20
Accepted
time: 0ms
memory: 3940kb
input:
4 274532062 833467053 -966615189 -925171401 990038689 -995756842 289416482 515357887 651324863 268351706 -185994232 777557885
output:
1428882748
result:
ok single line: '1428882748'
Test #36:
score: 20
Accepted
time: 2ms
memory: 5936kb
input:
100 999995897 999996781 387343302 999999437 999992610 527391011 999991947 999994474 -910551312 999999463 999999736 668118168 999993157 999994934 -920412353 999992157 999998105 -166875630 999994880 999994494 -34207478 999999548 999995286 186618265 999992504 999997869 -412394547 999993966 999990034 -1...
output:
5774783260
result:
ok single line: '5774783260'
Test #37:
score: 20
Accepted
time: 2ms
memory: 3976kb
input:
100 999996493 999999717 -472781015 999994959 999990741 140905225 999994650 999994580 -633697448 999991609 999990256 332595270 999994643 999992159 -940273142 999998356 999995944 820931402 999995182 999992871 49900922 999998560 999995066 -297060165 999995890 999993371 302610643 999991051 999990111 -39...
output:
5349621145
result:
ok single line: '5349621145'
Test #38:
score: 20
Accepted
time: 0ms
memory: 4344kb
input:
100 999996766 999992490 453505086 999991515 999990542 940427001 999994183 999999012 -11420484 999991487 999999611 -74233226 999996867 999994200 -806223556 999995705 999990016 -614835757 999990422 999996065 144991311 999991280 999995560 990904650 999993900 999994975 -861802403 999993320 999993206 -26...
output:
3677208423
result:
ok single line: '3677208423'
Test #39:
score: 20
Accepted
time: 2ms
memory: 3980kb
input:
100 999997304 999976132 722531352 999995107 999982170 169518745 999972891 999976540 952713688 999993563 999971110 685110355 999975695 999998656 -268303225 999984363 999985910 620513241 999989119 999971583 -904296386 999984254 999973568 12812482 999970839 999974417 -918339267 999993144 999977062 9276...
output:
5977105563
result:
ok single line: '5977105563'
Test #40:
score: 20
Accepted
time: 2ms
memory: 4332kb
input:
100 999999169 999999051 -383683652 999980959 999999507 -985348244 999997987 999984305 -25350871 999988229 999977309 -877856183 999977336 999982164 -54215005 999972699 999976042 -687614217 999977586 999974999 -878345275 999998495 999979978 -737327920 999995249 999975086 -827194141 999998566 999982667...
output:
6835367472
result:
ok single line: '6835367472'
Test #41:
score: 20
Accepted
time: 2ms
memory: 4232kb
input:
100 999984857 999985986 -640170026 999970636 999991681 -676962001 999978008 999994375 -510401729 999993558 999978346 29019591 999995453 999979390 846553934 999984894 999976018 620917572 999985305 999995323 -544989750 999984696 999996168 -283354913 999990215 999997907 185604996 999996904 999988593 -7...
output:
4333146486
result:
ok single line: '4333146486'
Test #42:
score: 20
Accepted
time: 2ms
memory: 3980kb
input:
100 999999225 -999991217 -208451264 999992954 -999993173 416922694 999998159 -999997404 -7404135 999996216 -999996287 -909575478 999998443 -999994770 -216976385 999999357 -999995920 -437809902 999992923 -999991958 -104610811 999998216 -999996127 -210240999 999996573 -999996419 798518635 999990507 -9...
output:
6523024049
result:
ok single line: '6523024049'
Test #43:
score: 20
Accepted
time: 2ms
memory: 4008kb
input:
100 999991776 -999999334 967640434 999991338 -999993172 -190186773 999990062 -999995602 519679311 999993594 -999999552 -401926815 999997113 -999992848 579378433 999998071 -999999690 -930880408 999994837 -999994533 397702683 999991376 -999992886 382330402 999991617 -999999191 458945774 999998597 -999...
output:
10455034037
result:
ok single line: '10455034037'
Test #44:
score: 20
Accepted
time: 2ms
memory: 4048kb
input:
100 999990286 -999994852 418625557 999995278 -999994649 129945246 999996539 -999990841 -75937765 999990452 -999996981 -993418764 999999229 -999999560 -681685649 999999663 -999998984 956379334 999994363 -999991640 678308115 999991506 -999995106 -190675279 999997499 -999994424 -933464751 999992765 -99...
output:
4984723336
result:
ok single line: '4984723336'
Test #45:
score: 20
Accepted
time: 2ms
memory: 4000kb
input:
100 999984725 -999988306 -536811057 999989661 -999999586 -340234339 999998996 -999970775 264227748 999995573 -999984228 453536486 999997386 -999978819 928661040 999997790 -999980588 -628632997 999979079 -999983304 8085365 999999712 -999992217 969211153 999982598 -999993819 -889278875 999985109 -9999...
output:
6632131603
result:
ok single line: '6632131603'
Test #46:
score: 20
Accepted
time: 2ms
memory: 5796kb
input:
100 999982110 -999986664 -183347253 999991601 -999999175 -530124722 999975963 -999991567 466307188 999972696 -999988507 -362668221 999997697 -999975276 938733865 999991769 -999982056 -423829892 999973857 -999990868 845614831 999979704 -999987802 743243029 999990551 -999972594 -779457843 999979873 -9...
output:
12863801465
result:
ok single line: '12863801465'
Test #47:
score: 20
Accepted
time: 2ms
memory: 3980kb
input:
100 999996945 -999978386 -264026779 999995629 -999975267 980854424 999993270 -999989144 486333529 999974511 -999989174 -37989197 999974214 -999989181 -673130656 999995518 -999994174 -966863873 999980794 -999998733 -51946365 999997607 -999992729 -955610480 999999807 -999993631 491683821 999988342 -99...
output:
6170174103
result:
ok single line: '6170174103'
Subtask #3:
score: 35
Accepted
Dependency #2:
100%
Accepted
Test #48:
score: 35
Accepted
time: 764ms
memory: 37416kb
input:
2000 89376854 379063415 -944003713 471827852 -789362482 -184369700 917771217 861434859 -951123027 388529816 150284383 863099328 -684844756 709695302 -812548755 -464667377 -991797883 -48791570 -100872644 745870335 301027897 863501557 763500779 -222414774 -778833050 168341796 277632677 -816853769 -167...
output:
31793047141
result:
ok single line: '31793047141'
Test #49:
score: 35
Accepted
time: 786ms
memory: 36748kb
input:
2000 389263830 -405935753 669574669 231558764 -947131817 896828872 10614352 -334835127 271062571 -709463869 -301280001 -402422121 -206698704 10932154 -536982687 -999203446 622875490 -227913333 -898072789 336971881 689463717 -667370995 527302553 229409694 -223794456 -692862768 132062784 -390582110 52...
output:
25091316125
result:
ok single line: '25091316125'
Test #50:
score: 35
Accepted
time: 778ms
memory: 36124kb
input:
2000 656797253 -862137230 -234043523 -392855847 -707119474 -69644067 -879345815 25802982 -692064663 -74494622 692754683 -694706582 455435039 93600817 -993077173 -202349503 -857906366 -339299335 648575352 -196151946 618875087 -681892593 163500612 -923627499 242854508 675676320 707970237 -207529106 -2...
output:
18009320601
result:
ok single line: '18009320601'
Test #51:
score: 35
Accepted
time: 765ms
memory: 35568kb
input:
2000 577751269 -43251297 230843756 -229600093 685116763 814906172 730195718 128177392 407299528 -539199892 749585566 523227707 -164767814 -553229511 138885675 600522468 -963411831 717083108 443420 43548728 -412257353 127987202 966308478 -943029928 -962260369 -417886812 -554925969 640137727 -39718847...
output:
19444086419
result:
ok single line: '19444086419'
Test #52:
score: 35
Accepted
time: 775ms
memory: 36576kb
input:
2000 -487456201 557789185 601546826 -162423750 -991036944 887305505 858117480 -882057181 577771086 872228962 -974871645 -281578647 -88250461 593508678 405875115 -742959507 474485293 -269269591 -936818455 385701404 496840214 -985344201 -69587834 44152735 -722595645 159891243 -729871649 -887249945 -36...
output:
20582127022
result:
ok single line: '20582127022'
Test #53:
score: 35
Accepted
time: 771ms
memory: 35852kb
input:
2000 391317570 300978285 -114343344 -622487600 -577364220 -920475742 -523275627 -32102300 -246508406 -198335805 435347164 -937944277 -14295989 237731607 -905368631 -112561816 740980183 -164029869 -274587726 -268803155 -423070063 -111960521 85783570 -944353391 -940713052 -929539615 766819748 -9499686...
output:
18386531871
result:
ok single line: '18386531871'
Test #54:
score: 35
Accepted
time: 778ms
memory: 35720kb
input:
2000 -792368730 -936925841 544557639 14833196 -987839772 -63764537 -963267147 -547912320 -818771536 902608780 -66346896 -387332838 -769657225 621473399 -39874228 22988194 -81004413 599394820 -41304045 121195969 780877464 -108857823 999151911 -73833894 -471986109 -321498373 -328542559 -104178173 1975...
output:
28424601936
result:
ok single line: '28424601936'
Test #55:
score: 35
Accepted
time: 784ms
memory: 36260kb
input:
2000 -505432619 224920488 -666042677 567983934 400619434 -893703875 203291563 341533353 671150754 -846711738 -983135334 678236454 -798667303 780661 -113162210 417973885 -279711184 -731257007 497081588 -622855336 -915437545 -775382145 -862623962 -526099979 -954618456 351683547 -118890763 941799916 -2...
output:
19594720787
result:
ok single line: '19594720787'
Test #56:
score: 35
Accepted
time: 770ms
memory: 36084kb
input:
2000 593058037 -616165164 -689956235 -633787314 -239404043 -39780003 274614032 801301679 -593789893 -498038356 -722310149 -53930341 -99563598 37943253 324813843 -840887657 258277545 -954869067 238012041 713231428 -222325888 218567416 -329609930 753148243 -849999907 -891548024 942878062 456613870 -17...
output:
19158237186
result:
ok single line: '19158237186'
Test #57:
score: 35
Accepted
time: 771ms
memory: 35908kb
input:
2000 264115998 -934167980 -820950350 403915714 338286714 950699345 788671388 -690831051 303295158 357890717 -896376056 -14613928 653139362 -685709439 -702106981 22157020 -804933352 -389253621 -212927690 -660397792 5348866 839066332 -945080086 -535751160 -883029915 272844657 -965281160 -843543315 800...
output:
21315828985
result:
ok single line: '21315828985'
Test #58:
score: 35
Accepted
time: 770ms
memory: 52664kb
input:
2000 990511917 996563274 306171535 997520630 994024333 87522652 993682462 993385589 795237259 992294005 994193875 660564229 998928373 996994107 -872206016 994633700 990499487 712687448 991056661 992946521 146767216 994250109 997312908 -698668153 999653807 993192254 601939659 997310617 995732171 2590...
output:
25663985651
result:
ok single line: '25663985651'
Test #59:
score: 35
Accepted
time: 773ms
memory: 51200kb
input:
2000 996536207 997357122 -116245278 999934801 994120481 354085898 990150173 997902936 516899726 991325478 990158866 -181768227 992436997 999254392 -800256736 996549149 994767211 -288191840 995947641 998526850 335560022 992941840 999607605 -362574082 994686482 997255234 346423912 990428276 995781528 ...
output:
15545836586
result:
ok single line: '15545836586'
Test #60:
score: 35
Accepted
time: 770ms
memory: 52820kb
input:
2000 992349050 993105825 146329182 999627245 996930433 -256304291 999852104 990435615 748499173 995014302 998387630 591115115 999700026 996890048 798641146 997258505 997982233 443895635 994822530 995300805 -744399570 992381224 991561910 -438005825 991223400 995494078 53771443 992782846 997279307 -58...
output:
16894409613
result:
ok single line: '16894409613'
Test #61:
score: 35
Accepted
time: 779ms
memory: 51036kb
input:
2000 985651994 998400727 515545987 995160785 988391020 297675159 984518003 982380763 -388305 981785563 998557052 665373037 991222886 983656225 -958138631 999438951 977564614 419270752 995942068 992552159 -836132023 976409235 988609237 -601015040 989744416 985447334 -6796065 984956182 975297233 63012...
output:
35214248927
result:
ok single line: '35214248927'
Test #62:
score: 35
Accepted
time: 773ms
memory: 51620kb
input:
2000 993790660 972639432 14581197 982876268 973516031 327798901 990452096 970739311 226379211 976882145 987494065 914263986 995926203 975602932 952932317 976488878 984947831 162116355 986757666 992543755 143036064 987162610 974511520 47677321 994331471 992415513 799848068 978099857 971807996 1630051...
output:
20670457767
result:
ok single line: '20670457767'
Test #63:
score: 35
Accepted
time: 761ms
memory: 51020kb
input:
2000 986277960 996598484 -510769637 989263736 984733600 -637163828 976755650 983127233 522615300 983163281 980160173 271630120 976521743 988780693 -429002498 985358376 996798678 -549713912 973734808 995291567 746081624 982508469 974912148 939245994 974610973 976566461 497768413 971492385 979867409 9...
output:
17527357231
result:
ok single line: '17527357231'
Test #64:
score: 35
Accepted
time: 763ms
memory: 52820kb
input:
2000 977801984 -972396500 401615273 984889952 -982886758 -357581924 986912276 -979767525 263316570 979710441 -994179107 -970727619 991808237 -997401644 -82845346 975157359 -991498342 -969190880 977792304 -979544824 -516268815 989935767 -998197433 470396855 991398212 -994267215 -706670977 987525283 -...
output:
15696292154
result:
ok single line: '15696292154'
Test #65:
score: 35
Accepted
time: 778ms
memory: 50724kb
input:
2000 975895298 -990624822 487331642 970641250 -986883202 -370347141 996862606 -995575074 671576120 985708217 -972896437 -558376306 988883980 -985763193 -514203049 996716167 -996869972 473956660 991843220 -979296345 134746102 979363805 -975807948 934201049 991919157 -981052287 -819306125 988261058 -9...
output:
23004753387
result:
ok single line: '23004753387'
Test #66:
score: 35
Accepted
time: 777ms
memory: 52636kb
input:
2000 991064440 -971614978 -88184580 980840764 -990505549 365425670 982391755 -977582852 593582448 970488263 -996189684 -622357344 984532395 -980027198 796222687 982358745 -987724939 -610722542 976705644 -975703663 312393521 978404011 -987388530 901121724 985820536 -970348376 168421109 990946269 -986...
output:
20915520790
result:
ok single line: '20915520790'
Test #67:
score: 35
Accepted
time: 766ms
memory: 50928kb
input:
2000 994036411 -995535827 78423809 998539593 -998520146 650595749 997315835 -994365029 482484768 994942296 -990545034 -667613979 996786613 -996143951 167320929 994031663 -993596723 -406663174 994989789 -995496904 -578922926 991115946 -993135451 633876289 999586074 -998270134 -753256882 997439140 -99...
output:
35600973826
result:
ok single line: '35600973826'
Test #68:
score: 35
Accepted
time: 771ms
memory: 53828kb
input:
2000 995867009 -998711791 495633259 994088544 -994331158 838516405 999504748 -993260689 771827153 994624846 -999493841 281179596 990247267 -999851641 566959052 995723770 -996378411 971877647 995585970 -990712408 263757014 998790445 -991375613 96012880 996613447 -991340800 690297951 999279257 -995350...
output:
23849714516
result:
ok single line: '23849714516'
Test #69:
score: 35
Accepted
time: 768ms
memory: 51704kb
input:
2000 994809106 -992929292 -520579214 998544947 -994516745 395090246 999334507 -996089848 870157418 995013935 -997159159 -953009312 997610460 -997308611 -161853188 996032205 -999211340 350230179 990327346 -993405677 -774990744 996116832 -991019124 -978885538 990711052 -990247750 -558160359 999361365 ...
output:
19085458863
result:
ok single line: '19085458863'
Subtask #4:
score: 20
Accepted
Dependency #3:
100%
Accepted
Test #70:
score: 20
Accepted
time: 778ms
memory: 37332kb
input:
2000 -745615874 -702990368 -552378840 -985596308 -859934968 85118341 -3804985 943674193 -826470074 282329143 482931997 608803157 797036847 564742842 -200664339 493906587 -213391618 574561504 -994907027 898746048 341190229 3160001 379059686 -846398007 924316391 253328091 900742158 -657453406 64342265...
output:
16455951810
result:
ok single line: '16455951810'
Test #71:
score: 20
Accepted
time: 780ms
memory: 36516kb
input:
2000 -894057416 -416689861 -548527712 -930830881 -851344157 205941590 510472024 24998858 -27101163 -567095873 219925055 -563341083 15159664 360474904 -906607326 274705185 997854812 -890942136 92774057 709226325 762828339 864878803 -706016445 -585962740 107972517 -170243102 917587025 -438922519 98151...
output:
22115506061
result:
ok single line: '22115506061'
Test #72:
score: 20
Accepted
time: 765ms
memory: 36204kb
input:
2000 790185670 -888961436 833335301 -442461598 105322929 -29832929 700123001 95631478 -794602330 -710251899 31244931 -320825164 353457886 910342867 810508990 -557416450 -971505865 -929939940 -219245863 525036552 -610849237 -247817681 234064465 86305098 -969255036 -660822782 839689223 -590930826 3231...
output:
24817841593
result:
ok single line: '24817841593'
Test #73:
score: 20
Accepted
time: 776ms
memory: 37232kb
input:
2000 -40269627 -869368636 199050976 -294835779 -485561905 108655517 -195943075 -928736449 -31161206 -160404496 -717921032 -545972434 317284440 -776334048 758737368 -954979104 -720719246 -447590265 59614381 -918066068 -772529248 74534180 197831758 -803966745 -984244281 -393255773 -575547406 -28289602...
output:
19586460728
result:
ok single line: '19586460728'
Test #74:
score: 20
Accepted
time: 774ms
memory: 36672kb
input:
2000 610984643 465097444 754183374 -382178935 -994857494 784394486 785817042 -848804062 798356159 810892177 85947902 786354129 -17078433 786233496 459137176 360125134 720540171 -375051694 383676278 -932204200 809509646 583762693 -513048685 423167652 -447927969 186152446 851613063 -85264229 331606653...
output:
22847613561
result:
ok single line: '22847613561'
Test #75:
score: 20
Accepted
time: 779ms
memory: 37160kb
input:
2000 -992887549 -145999639 -999219869 -701609123 -859554115 87188308 -24827431 372916278 797596246 -399873768 746049430 965111514 -267108314 279189871 -902937731 88247625 507248481 -973244511 332234996 333181458 -379383212 920827205 699886182 -343259021 -797779655 -177031180 -732869251 -694103951 -7...
output:
21003041048
result:
ok single line: '21003041048'
Test #76:
score: 20
Accepted
time: 769ms
memory: 37264kb
input:
2000 391718350 865785943 -616854395 -655423182 487673982 985696373 -403910619 -902563876 140245230 -779553356 793678008 -82050364 -269720949 643825503 -511175896 -373358813 -873198205 750344292 306961193 -988356485 -613337572 820338785 300949014 -480163301 -760784450 -219556736 431610537 -837301461 ...
output:
18181711298
result:
ok single line: '18181711298'
Test #77:
score: 20
Accepted
time: 764ms
memory: 35844kb
input:
2000 -777454075 680489075 663709094 -911471082 585067238 -637909393 802062638 920381535 -203008789 417874662 -278813945 276475119 -152095246 -885550630 286605834 968284371 281710287 500636929 956773250 935025939 495978766 -966855782 -187858165 187588469 -71405964 -999526795 -729638611 633170221 -676...
output:
24878244987
result:
ok single line: '24878244987'
Test #78:
score: 20
Accepted
time: 778ms
memory: 37696kb
input:
2000 -359315227 -580924835 523858265 -606483916 -820362702 -32138986 427307844 -948966070 198030369 -983575403 -414095184 -630205820 -371188834 756038317 438490163 -662470516 158347976 -892570977 -16495606 826860588 -434330902 -621456858 814427061 551722787 -578316968 -302064742 996146797 -938342871...
output:
18756048662
result:
ok single line: '18756048662'
Test #79:
score: 20
Accepted
time: 780ms
memory: 36216kb
input:
2000 -563167427 -870837325 -595855757 -57684738 -609413224 -926493576 -489333592 -994961033 -915079561 603123792 -655027785 216743207 -496519340 -154818679 -993249656 -462389297 396911440 -718369899 -517131492 529383083 636438219 -148509066 -415911431 42942789 -35327003 871870449 980286618 -20491356...
output:
24306792378
result:
ok single line: '24306792378'
Test #80:
score: 20
Accepted
time: 771ms
memory: 36584kb
input:
2000 982436812 -317444527 742958650 982436812 -587170901 -331507046 -86168003 -317444527 681591472 -86168003 -587170901 424873686 -791925120 949456201 -944659545 -791925120 -889357988 702589450 173367788 949456201 -923659798 173367788 -889357988 64342534 713072121 -521810898 983091417 713072121 -644...
output:
15309025284
result:
ok single line: '15309025284'
Test #81:
score: 20
Accepted
time: 769ms
memory: 36116kb
input:
2000 -175460887 918408096 654152079 -175460887 -659389794 -206522608 -539931189 918408096 419820488 -539931189 -659389794 -427224787 -451748220 177253373 -224234897 -451748220 595723014 -992540857 514873182 177253373 -917241154 514873182 595723014 -437034119 -953570575 -872009064 826825132 -95357057...
output:
18316938113
result:
ok single line: '18316938113'
Test #82:
score: 20
Accepted
time: 758ms
memory: 36568kb
input:
2000 929506214 -374268787 -145650893 929506214 -943866026 621698368 -694585193 -374268787 36214976 -694585193 -943866026 -706612249 -323806375 886787248 -109886728 -323806375 496729840 -920170969 -905035588 886787248 -449256488 -905035588 496729840 -666678156 -926417238 -575838823 938890575 -9264172...
output:
24120299057
result:
ok single line: '24120299057'
Test #83:
score: 20
Accepted
time: 774ms
memory: 36040kb
input:
2000 -718323966 -199413467 -322187822 -718323966 -896414615 708895058 998476049 -199413467 -177348657 998476049 -896414615 -873846517 -361609724 754103231 245231199 -361609724 254463734 -181134625 -7143630 754103231 529833759 -7143630 254463734 795449391 -933739742 265812107 275612513 -933739742 739...
output:
20902198154
result:
ok single line: '20902198154'
Test #84:
score: 20
Accepted
time: 769ms
memory: 36360kb
input:
2000 386542071 -9993314 -666187901 386542071 389153961 -96874208 268499250 -9993314 148998752 268499250 389153961 94013888 -656901707 -846291271 151421027 -656901707 -867478042 -90144765 45455941 -846291271 911610308 45455941 -867478042 -197208665 701219965 -545599399 465015367 701219965 147214482 4...
output:
21260050640
result:
ok single line: '21260050640'
Test #85:
score: 20
Accepted
time: 768ms
memory: 36716kb
input:
2000 742425215 -913755530 807508655 742425215 -757637489 -617247769 -359953185 -913755530 -890552539 -359953185 -757637489 907934908 758758561 176322731 -899927733 758758561 519647987 256153091 -999278176 176322731 269957556 -999278176 519647987 -744483079 -72780220 282617934 18694511 -72780220 6218...
output:
16463237834
result:
ok single line: '16463237834'
Test #86:
score: 20
Accepted
time: 795ms
memory: 36252kb
input:
2000 -962782508 -334426819 522129758 -962782508 -279456436 -79796187 -44851658 -334426819 -133134784 -44851658 -279456436 375088034 -417331929 39483581 -983011569 -417331929 286900264 192505029 -305735898 39483581 -925467054 -305735898 286900264 -182025385 811877986 -93542420 708507276 811877986 -60...
output:
21823162926
result:
ok single line: '21823162926'
Test #87:
score: 20
Accepted
time: 770ms
memory: 36864kb
input:
2000 606481993 392216380 -948731759 606481993 -252361914 -934714511 -404434507 392216380 576766384 -404434507 -252361914 -78755056 -817090544 -548612027 54978386 -817090544 786740050 931071982 881096559 -548612027 537504845 881096559 786740050 590260335 862582814 -961616879 -456167556 862582814 -159...
output:
24461735670
result:
ok single line: '24461735670'
Test #88:
score: 20
Accepted
time: 778ms
memory: 35616kb
input:
2000 155073010 -42419615 536002195 155073010 -984203132 676209633 390137124 -42419615 925748001 390137124 -984203132 269211710 -686427461 -462753083 768833589 -686427461 296369340 -918379193 264143046 -462753083 -464058079 264143046 296369340 886161191 -954629099 -622171310 -914999202 -954629099 719...
output:
18807666237
result:
ok single line: '18807666237'
Test #89:
score: 20
Accepted
time: 769ms
memory: 36192kb
input:
2000 -802541145 -758004606 -211473031 -802541145 -945245162 -289279605 -518277190 -758004606 -164014650 -518277190 -945245162 104199658 -159623565 327712784 782541362 -159623565 -598949537 256903485 667190210 327712784 722382311 667190210 -598949537 -963058302 487683708 -955694932 661010141 48768370...
output:
24026700278
result:
ok single line: '24026700278'
Subtask #5:
score: 20
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #90:
score: 20
Accepted
time: 773ms
memory: 36592kb
input:
2000 -518317848 495146109 -207298065 -101593293 -792312795 731805935 -497518542 541307 66180594 -682026897 -960359907 -1361359 760520470 338148758 263030572 651535375 -565107329 -855066275 -987696031 -873379670 420778167 530279019 -856211499 -528324989 -440408764 -89596927 -347682476 584719703 66986...
output:
17438340652
result:
ok single line: '17438340652'
Test #91:
score: 20
Accepted
time: 778ms
memory: 36256kb
input:
2000 -871312852 -185153055 982602299 52220124 -726330649 -759138203 906866733 387781179 -856036035 97060093 -900674842 -22852752 646629471 -459703086 545703314 645769019 -744537701 -905816086 -417660671 280648504 803840133 -455231813 17887670 -850834641 303629036 -886292375 476146649 -504572562 8982...
output:
25233348005
result:
ok single line: '25233348005'
Test #92:
score: 20
Accepted
time: 779ms
memory: 36804kb
input:
2000 -257296694 -891659871 266448530 -488838642 280118693 367614497 -856347520 -103986549 -998905301 -820687770 -537722451 -615105658 935033072 -160502979 585577347 -782579503 -896534201 771782810 863935777 -84614714 456376268 60956052 939017028 521031148 828214665 -725832710 -712860644 714394562 -2...
output:
25236885275
result:
ok single line: '25236885275'
Test #93:
score: 20
Accepted
time: 776ms
memory: 37168kb
input:
2000 -685252066 -119642501 -184788492 -893814222 -937507623 329158282 -653585194 492522191 -482750016 -684494358 160759679 -242250844 -438874056 -621458765 -701365241 -391781034 175465258 156443479 228773980 -255184010 98967021 632921138 118504400 39542022 -457549083 -945657664 -732919051 -898319139...
output:
19714745596
result:
ok single line: '19714745596'
Test #94:
score: 20
Accepted
time: 780ms
memory: 35856kb
input:
2000 240992379 574760775 284471395 -683096465 87422414 697799258 -93183393 -700461659 -206546507 -557828395 506363307 786302256 635863582 670235168 851540313 410756728 -401451735 -626390642 -309710346 549068544 -792068758 -948847408 -891691815 553866888 -607423852 -916111748 209678131 -994772405 357...
output:
25006242157
result:
ok single line: '25006242157'
Test #95:
score: 20
Accepted
time: 774ms
memory: 36044kb
input:
2000 -580361292 744960939 24750183 -983963193 -81001913 100695638 736477447 -857043217 530880606 478115352 801515188 -314454741 -215428826 965315797 -215870894 276054359 979191185 -252138354 -442629927 -867030281 137261942 -481776430 554965854 -854432575 -942852074 -950917623 -912661379 -121618998 -...
output:
19674844429
result:
ok single line: '19674844429'
Test #96:
score: 20
Accepted
time: 775ms
memory: 37656kb
input:
2000 -467689921 -868716149 -219811992 -138592478 43446661 -867260093 107784491 -117370344 -895942615 -452337728 -190724948 -947367475 -3779074 -531210537 709871422 -400224605 463111972 -246136861 94032899 177520008 345783037 699682674 -914584679 -853859488 656655453 -386742599 625127321 -163989889 3...
output:
17672516509
result:
ok single line: '17672516509'
Test #97:
score: 20
Accepted
time: 772ms
memory: 36528kb
input:
2000 -857694017 -265709069 379836982 -92044153 390359225 -958176485 882418639 -630539775 510887987 -862014059 462730210 -36462020 -337893884 -982880128 -883044266 -603636045 -554944356 -968647085 428098639 -410287299 317675103 -21338075 151904505 65745626 -846662323 325529657 795983278 -668115820 -6...
output:
19189973307
result:
ok single line: '19189973307'
Test #98:
score: 20
Accepted
time: 764ms
memory: 36964kb
input:
2000 -687642777 -143501507 -533386038 431548181 -346590632 345696700 -987192893 929227627 -943168785 -810597254 -484563442 -771594985 -659554793 978526931 -905648432 -591837217 -678420569 255150609 33703581 -759176797 227359655 920190463 -709415081 644218673 792222655 123099080 686932034 -263532955 ...
output:
25523782582
result:
ok single line: '25523782582'
Test #99:
score: 20
Accepted
time: 777ms
memory: 36756kb
input:
2000 -3334358 123750419 879894703 -70892073 -214034802 -552420806 -245674316 387381496 -772168135 349812339 458781234 -898201819 232857090 303800807 144212042 235788167 -904300352 583673020 466358184 990247908 -909854055 636863506 -546435666 740831078 835207268 -591742922 -393176282 365376344 632479...
output:
21105791089
result:
ok single line: '21105791089'
Test #100:
score: 20
Accepted
time: 356ms
memory: 20132kb
input:
2000 1 -884364402 432900700 0 910446467 -87652277 1 178082533 -143565280 0 -523482816 -725527016 0 -914737760 950767216 1 -460505729 -961351602 0 177466077 787693692 1 217138121 133974210 0 283345955 -963782784 0 262389748 -888359636 0 321710867 959884174 1 163116603 924900443 0 482608983 -852764847...
output:
19421250700
result:
ok single line: '19421250700'
Test #101:
score: 20
Accepted
time: 362ms
memory: 21652kb
input:
2000 0 787025206 -368741109 0 -903020474 -493995880 1 -31987439 890962124 0 364599472 883566613 0 -258564072 -88950089 0 433092014 223931044 1 -740163125 -854673723 1 -528621291 328639968 0 579814454 -693578675 1 797454572 856354605 0 -884889654 -897438965 1 -630261108 -818116960 0 -32626962 -237550...
output:
18910751154
result:
ok single line: '18910751154'
Test #102:
score: 20
Accepted
time: 354ms
memory: 21656kb
input:
2000 0 -419679076 648884749 1 -440891006 845861700 1 -445932836 -658529217 1 44329765 630926851 1 716290787 326146391 0 213384510 -469538035 0 331591417 -787293348 1 -470020112 -449854358 0 -454530148 -607946868 0 -855765086 -211324539 1 -485533765 699679623 0 -77643659 -461301688 1 -854584313 -8801...
output:
14977624627
result:
ok single line: '14977624627'
Test #103:
score: 20
Accepted
time: 362ms
memory: 21528kb
input:
2000 1 464790641 -629876577 1 734690390 884081552 0 -689638437 399752853 1 876104833 642806446 1 -302191431 -702401557 0 -460729654 358939569 0 -594676446 774338453 0 -445630358 -341911180 1 692077545 1474390 0 -725716663 838403532 1 -450843006 995559062 0 -644400838 -660044322 1 972665730 877614911...
output:
20204536731
result:
ok single line: '20204536731'
Test #104:
score: 20
Accepted
time: 360ms
memory: 20024kb
input:
2000 1 -698446279 -365518395 0 951191650 692849816 0 -700734687 -326505330 1 637328332 71762239 1 -339595897 -158837071 1 -389110940 -534172701 0 988434532 -907414271 0 -681892992 -798549373 0 85684500 -915065140 0 -733190856 -906857197 0 -640109229 365509439 0 487882291 -919847594 0 945593561 -1766...
output:
16473764294
result:
ok single line: '16473764294'
Test #105:
score: 20
Accepted
time: 489ms
memory: 25552kb
input:
2000 2 550966856 -168401350 2 700910612 34731691 2 975354208 373772206 1 -975641088 439003337 1 -902828909 955948044 2 -197913989 -750343002 2 -346769937 -801609001 2 907402971 402541173 1 -704729503 -366326484 2 721322519 -501744890 2 -32942336 -596571741 1 99254083 -986937901 1 385722508 -7614385 ...
output:
25683926602
result:
ok single line: '25683926602'
Test #106:
score: 20
Accepted
time: 485ms
memory: 25972kb
input:
2000 0 -62751934 -934320645 0 904621791 -936128275 0 -948981002 -993871129 0 -848501919 -351136491 2 543802527 136673463 1 957337515 -967406978 2 130595015 -405280902 2 830018325 -907580905 2 399357292 384861029 0 -925243904 84607555 0 -980342449 744117720 1 394510358 -590596627 2 113906500 -7965937...
output:
18448634540
result:
ok single line: '18448634540'
Test #107:
score: 20
Accepted
time: 490ms
memory: 25508kb
input:
2000 0 -73658527 -111886062 0 -848868145 -391161559 1 49589273 -269340654 1 564539610 -771342810 1 71447952 218480501 1 -810231710 -608626872 1 -262722292 108552226 0 -513189601 -250516093 2 752540038 272955410 2 -967022662 924234261 1 -269990133 -95380629 1 -344824711 -941457114 2 358657732 -986429...
output:
17796796237
result:
ok single line: '17796796237'
Test #108:
score: 20
Accepted
time: 490ms
memory: 26052kb
input:
2000 0 767348942 -939939969 0 994908103 -787235843 2 -806074413 -413238639 2 369278225 -838910823 2 613730065 -994152056 0 718537113 792271580 0 -886215405 -978783649 2 -244679400 -879261528 2 -697135782 4683397 0 944053500 -370148763 1 -251765516 -520814833 1 661927284 -356460857 1 -583194043 71447...
output:
19156458539
result:
ok single line: '19156458539'
Test #109:
score: 20
Accepted
time: 489ms
memory: 25012kb
input:
2000 0 -378210877 669437950 0 800327421 -893226080 1 -973930339 350564274 2 -346914520 -892277343 1 -294590653 -150701798 1 -976143409 -190661012 2 -136380397 -823743938 0 -465186439 -686438890 2 963973622 159738395 1 -834203895 -93074209 0 925868454 -788919551 0 -832260996 595485163 0 -917967748 -8...
output:
22425430628
result:
ok single line: '22425430628'
Test #110:
score: 20
Accepted
time: 528ms
memory: 36264kb
input:
2000 762985073 204725240 487905292 282466160 -855464145 465576844 -669259936 -887601486 566505569 -947036571 389107240 -957695302 8652456 -341541838 -892929561 233497717 544585352 -414340881 489630665 -384580342 -488659383 521545793 736379548 -318890318 853042717 622602801 672409936 619088384 -43305...
output:
18867712371
result:
ok single line: '18867712371'
Test #111:
score: 20
Accepted
time: 534ms
memory: 36628kb
input:
2000 -287463896 129262991 -239985274 -614405338 -638529640 -243299823 318763314 624161282 -878520998 -626945623 -624944516 395088433 517843191 -893307158 797458417 -659855474 80007874 -76640482 867464914 -855719371 430274113 693638873 525976921 -175676832 -481057608 805234059 -362065090 162746254 77...
output:
19122874709
result:
ok single line: '19122874709'
Test #112:
score: 20
Accepted
time: 526ms
memory: 37496kb
input:
2000 627014823 366948176 710441442 633158917 -883856076 84645271 249534995 -747302171 473374371 848936242 -191787854 706138774 -149936525 715754893 287328460 299983661 -762000600 -132498881 -798904891 131899103 -969996981 785666375 -978370047 253659937 133706273 614803097 610626615 797920143 -124346...
output:
21697531281
result:
ok single line: '21697531281'
Test #113:
score: 20
Accepted
time: 538ms
memory: 36884kb
input:
2000 214754462 487341732 -385844478 158181260 -331329725 160897202 -82134326 -542418569 -241724856 106587499 -773460941 604364083 -341066593 579345317 -124215496 -372734777 542206898 384420046 -953923362 -317369247 686268781 679739241 -939144122 -40310137 -688938233 176576772 -92715951 -368166597 -6...
output:
24286032504
result:
ok single line: '24286032504'
Test #114:
score: 20
Accepted
time: 539ms
memory: 34860kb
input:
2000 685071613 -598839495 -210590135 -422570680 -353859765 893227997 -217530297 -932431716 -340851578 -985409145 174844908 175456802 183407745 708007021 952506182 657996665 -22596842 396519631 -579956310 667666395 474372568 161997258 -670030054 266570938 -931695099 -770276823 -865638223 -477258708 -...
output:
19034231255
result:
ok single line: '19034231255'
Test #115:
score: 20
Accepted
time: 532ms
memory: 35240kb
input:
2000 -901099292 -320428674 -283111025 -835321935 -856191047 -958922827 -640125063 111939765 -656146991 825543403 -914308892 -874804097 -857155289 407908115 459903943 -968158151 -292377627 -166418911 666436707 438398118 -709470615 -103917182 277038724 763773297 229901248 655651361 -93286207 -47185268...
output:
16677855936
result:
ok single line: '16677855936'
Test #116:
score: 20
Accepted
time: 540ms
memory: 35220kb
input:
2000 -861000123 -858764767 -272522240 467057592 932230743 370359623 927063413 -213562328 643476307 581160391 -876947460 626537076 -642733359 -984705100 -692636362 953235119 -13618326 -839377389 -877061894 182679151 -913212647 -128793291 784694659 -980277774 -543451087 917122184 644225477 -993320450 ...
output:
16856131313
result:
ok single line: '16856131313'
Test #117:
score: 20
Accepted
time: 536ms
memory: 34680kb
input:
2000 -311976416 -832974973 -370451089 -211604967 881491311 -573636139 -489960222 366236165 181377472 272374984 236701408 -475170199 316125172 -48204930 -222569565 388912504 982912108 165943779 -420341253 -786680917 -882642243 -524191757 -991847963 -359312884 387109126 -177342481 -201061854 629256098...
output:
24282628849
result:
ok single line: '24282628849'
Test #118:
score: 20
Accepted
time: 533ms
memory: 35468kb
input:
2000 -951318742 448417998 -792358680 461213505 732428760 -73659725 -335000325 858866308 -669369829 788922767 877871272 -240496850 344797982 165246268 247310777 65545360 -994915074 -81162600 -868110212 -592125521 17067602 -903310588 244263295 -727618975 3905999 -238667092 722138547 493156139 -5559333...
output:
26118298657
result:
ok single line: '26118298657'
Test #119:
score: 20
Accepted
time: 533ms
memory: 35136kb
input:
2000 -935066165 233857309 -890883193 -988360898 -222712112 692621714 -678536472 -400824514 -985179664 -53970339 126385941 -173839216 259983808 601008629 131906331 334604071 -826006525 634502231 -670304590 665397573 66024559 -210385887 423350269 -198452532 -264013858 271194475 946492080 -42744808 -92...
output:
17214578697
result:
ok single line: '17214578697'
Test #120:
score: 20
Accepted
time: 0ms
memory: 4220kb
input:
6 -1000000000 -1000000000 1 -1000000000 0 1 -1000000000 999999999 1 1000000000 -999999999 -1 999999999 1 1 999999998 1000000000 -1
output:
4
result:
ok single line: '4'
Test #121:
score: 20
Accepted
time: 0ms
memory: 3952kb
input:
6 -1000000000 -1000000000 1 -1000000000 0 1 -1000000000 999999999 1 1000000000 -999999999 -1 1000000000 1 1 1000000000 1000000000 -1
output:
3
result:
ok single line: '3'
Test #122:
score: 20
Accepted
time: 789ms
memory: 53076kb
input:
2000 999999453 999998622 -695821416 999998279 999998844 599077495 999999082 999998002 239162136 999999831 999998414 -982662521 999998867 999998993 -696308112 999998524 999998139 615942646 999998258 999998248 -877445109 999998125 999999515 503334149 999999222 999998911 155618694 999998776 999999642 -...
output:
27167565262
result:
ok single line: '27167565262'
Test #123:
score: 20
Accepted
time: 763ms
memory: 51392kb
input:
2000 999999021 999998785 53318669 999999556 999999010 83477766 999999544 999999998 -932887917 999999019 999999950 882644690 999998902 999998276 -148027134 999998375 999998406 -896802332 999999236 999999159 230583008 999998975 999999377 -626946040 999999163 999998674 446787831 999999638 999998102 151...
output:
21364643104
result:
ok single line: '21364643104'
Test #124:
score: 20
Accepted
time: 766ms
memory: 51924kb
input:
2000 999999862 999998209 -369937948 999999179 999999397 486431655 999998705 999998098 -972065988 999998490 999999312 210853501 999999382 999999913 250075596 999998093 999999873 -837090212 999999132 999999911 72845056 999999542 999999727 -363642192 999999096 999999348 398329114 999999715 999999826 62...
output:
25281522679
result:
ok single line: '25281522679'
Test #125:
score: 20
Accepted
time: 767ms
memory: 51248kb
input:
2000 999999516 999997884 -332143266 999997704 999999790 62613498 999998096 999998505 245182594 999997487 999999321 -764456409 999998752 999999800 474401130 999999266 999997588 385700668 999999563 999998157 491592532 999997434 999997901 -938170462 999999434 999997316 417103815 999997689 999997487 -59...
output:
20039666309
result:
ok single line: '20039666309'
Test #126:
score: 20
Accepted
time: 760ms
memory: 51980kb
input:
2000 999997018 999999686 -891900876 999998639 999999597 -579723644 999997306 999999310 871067540 999997676 999997311 162377255 999998224 999999180 485739225 999999016 999997088 -961119402 999998584 999997681 -770256339 999997525 999999621 165499363 999997496 999997110 -554386192 999997515 999997872 ...
output:
27775001813
result:
ok single line: '27775001813'
Test #127:
score: 20
Accepted
time: 766ms
memory: 52224kb
input:
2000 999999925 999998925 359048455 999999328 999998076 -69453915 999997709 999997291 198153855 999999767 999998857 -902689910 999999633 999999541 -925142816 999997067 999999114 -312253904 999999975 999997485 -235556839 999999496 999998836 -591329473 999998724 999998035 786761538 999997719 999998494 ...
output:
22635860826
result:
ok single line: '22635860826'
Test #128:
score: 20
Accepted
time: 770ms
memory: 52196kb
input:
2000 999998194 -999998422 546205681 999999542 -999999838 -283682496 999998553 -999999397 -571616463 999999314 -999997887 273715597 999999516 -999999645 -641457645 999997990 -999998440 -403178123 999998525 -999997924 198209702 999998149 -999999960 -815309461 999997268 -999997262 758514601 999999221 -...
output:
24122920279
result:
ok single line: '24122920279'
Test #129:
score: 20
Accepted
time: 758ms
memory: 51708kb
input:
2000 999997559 -999998929 -561025015 999997921 -999999930 945538548 999999022 -999998476 399098794 999997979 -999998354 -671281619 999999255 -999998766 -790369220 999999970 -999997887 339224589 999999213 -999999139 -91222622 999997220 -999999731 -255485190 999998231 -999999115 -426957896 999998770 -...
output:
21226363175
result:
ok single line: '21226363175'
Test #130:
score: 20
Accepted
time: 760ms
memory: 52208kb
input:
2000 999998096 -999999967 834911236 999999228 -999998831 -704923065 999997960 -999997852 390458782 999997267 -999998986 -897997641 999999163 -999998371 -486007753 999999849 -999998295 -253390773 999997148 -999998141 565703373 999999700 -999997079 -880862992 999999310 -999997127 893099862 999998601 -...
output:
26664405762
result:
ok single line: '26664405762'
Test #131:
score: 20
Accepted
time: 767ms
memory: 52664kb
input:
2000 999997084 -999999876 -688231367 999993474 -999997528 818725545 999998216 -999998676 -959033206 999992771 -999991481 80795621 999990303 -999997456 -973824197 999993514 -999993831 856392137 999995008 -999999989 574266326 999999093 -999995703 542375081 999991598 -999999092 -939560515 999997715 -99...
output:
17560924602
result:
ok single line: '17560924602'
Test #132:
score: 20
Accepted
time: 768ms
memory: 51588kb
input:
2000 999998691 -999991923 973529106 999990874 -999992852 -275119849 999999941 -999999381 696615332 999997996 -999994021 761517863 999996852 -999994968 993558879 999993492 -999990767 -220954951 999998818 -999991990 610038648 999996759 -999999666 -22484261 999998373 -999991666 -410876502 999991748 -99...
output:
25146105296
result:
ok single line: '25146105296'
Test #133:
score: 20
Accepted
time: 767ms
memory: 54080kb
input:
2000 999994147 -999991440 -846496532 999999061 -999992173 541474879 999997229 -999993057 -981539491 999999913 -999999793 591121016 999996513 -999993706 -274588057 999997527 -999999233 -132330085 999993294 -999997000 931564125 999990127 -999996951 888434560 999993030 -999993609 -388668064 999998556 -...
output:
21535508556
result:
ok single line: '21535508556'
Extra Test:
score: 0
Extra Test Passed