akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n);
	rep(i,n) cin >> a.at(i) >> b.at(i) >> c.at(i);
	vector<vector<int>> dp(3,vector<int>(n+2));
	rep(i,n){
		dp[0][i+1]=max(dp[0][i+1],max(dp[1][i]+a.at(i),dp[2][i]+a.at(i)));
		dp[1][i+1]=max(dp[1][i+1],max(dp[0][i]+b.at(i),dp[2][i]+b.at(i)));
		dp[2][i+1]=max(dp[2][i+1],max(dp[0][i]+c.at(i),dp[1][i]+c.at(i)));
	}
	cout << max(dp[0][n],max(dp[1][n],dp[2][n])) << endl;
}

Measured memory_bytes: 2944
#include<stdio.h>
int main(void){
    while(1){
        long long int ans=0;
        int i,hoge,hogehoge=1000;
        char input;
        while(1){
            if(scanf("%c",&input)==EOF)goto END;
            else if(input=='\n')break;
            if(input=='I')hoge=1;
            else if(input=='V')hoge=5;
            else if(input=='X')hoge=10;
            else if(input=='L')hoge=50;
            else if(input=='C')hoge=100;
            else if(input=='D')hoge=500;
            else if(input=='M')hoge=1000;
            ans+=hoge;
            if(hoge>hogehoge){
                ans-=hogehoge*2;
            }
            hogehoge=hoge;
        }
        printf("%d\n",ans);
    }
    END:
    return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
using namespace std;

int main(void){
int n;
cin>>n;
vector<pair<int,int> > data(n);
for(int i=0;i<n;i++){
	int a,b;
	cin>>a>>b;
	data[i]=make_pair(a,b);
}
int amaxi=0;
sort(data.begin(),data.end());
long long ans=0;
ans+=data[n-1].first;
ans+=data[n-1].second;
cout<<ans;
return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;
const ll INF = 1LL << 60;
#define MOD 1000000007
#define MAX_V 100010
#define MAX_N 100010

bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}

ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

ll junnretu(ll n){
    ll ans=1;
    for (ll i=1;i<=n;i++){
        ans*=i;
    }
    return ans;
}

int main(){
    string s;
    cin >> s;
    ll ans=INF;
    for (ll i=0;i<s.size()-2;i++){
        ll x=(s[i]-'0')*100+(s[i+1]-'0')*10+(s[i+2]-'0');
        ans=min(ans,abs(753-x));
    }
    cout << ans << endl;
    return 0;
}





Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

int main() {
    int N;
    cin >> N;
    cout << N / 3 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(){
    string n;

    while(cin>>n){
        for(int i=0; i<n.size(); i++){
            if(n[i]=='1')
                n[i] = '9';
            else if(n[i]=='9')
                n[i] = '1';
        }
        cout<<n<<endl;
    }
}



Measured memory_bytes: 256
N = int(input())
lis = list(map(int, input().split()))
rt = 0
for i in range(0,N-2,1):
  for j in range(i+1,N-1,1):
    for k in range(j+1,N,1):
      if (
          lis[k]+lis[j] > lis[i]
          and lis[i]+lis[k] > lis[j]
          and lis[i]+lis[j] > lis[k]
          and lis[i] != lis[j]
          and lis[j] != lis[k]
          and lis[k] != lis[i]):
        rt+=1
print(rt)

Measured memory_bytes: 9204
N = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

cluster_two = 0
cluster_one = 0

for i in range(N):
    if A[i] < B[i]:
        cluster_two += (B[i]-A[i])//2
    elif A[i] > B[i]:
        cluster_one += A[i]-B[i]

if cluster_two >= cluster_one:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 4724
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define d(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

string s,os,te="";
int main(void){
    cin>>os;
    s=os;
    LL c,si=SZ(s),sum=0,l=0,j;
    REP(i,1<<(si-1)){
        c=0;
        s=os;
        for(j=0;j<si;j++){
            if(1&i>>j){
                sum+=stoi(s.substr(l,j+1-l));
                l=j+1;
            }
        }
        sum+=stoll(s.substr(l,s.size()-l));
        l=0;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef long long ll;

int n, k;
ll a, b;

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		if (i%k == 0) a++;
		if (i%k != 0 && (2*i)%k == 0) b++;
	}
	cout << a*a*a+b*b*b << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    map<ll, ll, greater<ll>> cnt;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        cnt[A[i]]++;
    }

    for (int i = 0; i < M; i++) {
        ll b, c;
        cin >> b >> c;
        cnt[c] += b;
    }

    ll ans = 0;
    ll rest = N;
    for(auto e : cnt) {
        ll c = min(rest, e.second);
        ans += e.first * c;
        rest -= c;
        if (!rest) break;
    }
    cout << ans << endl;

}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

Measured memory_bytes: 13568
N = int(input())
# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]

if 100 <= N <= 105:
    print(1)
    exit(0)
elif 200 <= N <= 210:
    print(1)
    exit(0)
elif 300 <= N <= 315:
    print(1)
    exit(0)
elif 400 <= N <= 420:
    print(1)
    exit(0)
elif 500 <= N <= 525:
    print(1)
    exit(0)
elif 600 <= N <= 630:
    print(1)
    exit(0)
elif 700 <= N <= 735:
    print(1)
    exit(0)
elif 800 <= N <= 840:
    print(1)
    exit(0)
elif 900 <= N <= 945:
    print(1)
    exit(0)
elif 1000 <= N <= 1050:
    print(1)
    exit(0)
elif 1100 <= N <= 1155:
    print(1)
    exit(0)
elif 1200 <= N <= 1260:
    print(1)
    exit(0)
elif 1300 <= N <= 1365:
    print(1)
    exit(0)
elif 1400 <= N <= 1470:
    print(1)
    exit(0)
elif 1500 <= N <= 1575:
    print(1)
    exit(0)
elif 1600 <= N <= 1680:
    print(1)
    exit(0)
elif 1700 <= N <= 1785:
    print(1)
    exit(0)
elif 1800 <= N <= 1890:
    print(1)
    exit(0)
elif 1900 <= N <= 1995:
    print(1)
    exit(0)
elif 2000 <= N:
    print(1)
    exit(0)
else:
    print(0)


Measured memory_bytes: 38256
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""
各マスのdp
下から来たものと左から来たものを足す
その後、重なっているところを引く
"""
MOD = 998244353
A, B, C, D = lr()  # Cは縦
dp = [[0] * (D+1) for _ in range(C+1)]   # 1-indexed
dp[A][B] = 1
for i in range(A, C+1):
    for j in range(B, D+1):
        if i == A and j == B:
            continue
        dp[i][j] = dp[i-1][j] * j + dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= MOD

answer = dp[C][D]
print(answer%MOD)


Measured memory_bytes: 133924
#include<bits/stdc++.h>
using namespace std;int n,i;

main(){
	
	cin>>n;
	long a[n];
	for(;i<n;cin>>a[i],i++);
	for(sort(a,a+n);i-1;(*a*=__gcd(a[n-i+1],n-i+1l))%=998244353,i--);
	cout<<*a;
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(){
	int x;
	int y;
	y = 1;
	while(true){
		cin >> x >> y;
		
		if( x == 0 && y == 0){ break;};
		if(x>y){
			cout << y <<" "<< x <<endl;
		}
		else{
			cout << x <<" " << y <<endl;
		};
	}
	
	return 0;
}

Measured memory_bytes: 1160
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<algorithm>
typedef signed long long int int64;
inline unsigned getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register unsigned x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
inline int64 min(const int64 &a,const int64 &b) {
	return a<b?a:b;
}
const int64 inf=0x7ffffffffffffff;
const int N=200001;
int n;
class FenwickTree {
	private:
		int64 val[N];
		int lowbit(const int &x) const {
			return x&-x;
		}
	public:
		FenwickTree() {
			std::fill(&val[0],&val[N],inf);
		}
		void modify(int p,const int64 &x) {
			while(p<=n) {
				if(x<val[p]) {
					val[p]=x;
				} else 
				p+=lowbit(p);
			}
		}
		int64 query(int p) const {
			int64 ret=inf;
			while(p) {
				ret=min(ret,val[p]);
				p-=lowbit(p);
			}
			return ret;
		}
};
FenwickTree ta;
class RevFenwickTree {
	private:
		int64 val[N];
		int lowbit(const int &x) const {
			return x&-x;
		}
	public:
		RevFenwickTree() {
			std::fill(&val[0],&val[N],inf);
		}
		void modify(int p,const int64 &x) {
			while(p) {
				if(x<val[p]) {
					val[p]=x;
				}
				p-=lowbit(p);
			}
		}
		int64 query(int p) const {
			int64 ret=inf;
			while(p<=n) {
				ret=min(ret,val[p]);
				p+=lowbit(p);
			}
			return ret;
		}
};
RevFenwickTree tb;
int64 f[N];
inline void modify(const int &p,const int64 x) {
	if(x<f[p]) {
		f[p]=x;
		ta.modify(p,x-p);
		tb.modify(p,x+p);
	}
}
int main() {
	n=getint();
	int q=getint(),a=getint(),b=getint();
	std::fill(&f[0],&f[N],inf);
	modify(a,0);
	int64 sum=0;
	while(q--) {
		a=b;
		b=getint();
		sum+=abs(a-b);
		int64 t1=ta.query(b)+b,t2=tb.query(b)-b;
		modify(a,min(t1,t2)-abs(a-b));
	}
	int64 tmp=inf;
	for(register int i=1;i<=n;i++) {
		tmp=min(tmp,f[i]);
	}
	printf("%lld\n",tmp+sum);
	return 0;
}


Measured memory_bytes: 4864
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int main(void){
	int n;
	int a=0, ans = 0;
	scanf("%d",&n);
	int t[100001]={};
	for(int i=0; i<n; i++){
		scanf("%d",&a);
		t[a]++;
	}
	for(int i=1; i<100000; i++){
		ans = max(ans, t[i-1]+t[i]+t[i+1]);
	}
	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 640
N=int(input())
Ss = []
Ts = []
for _ in range(N):
    S,T = input().split()
    Ss.append(S)
    Ts.append(int(T))

END = input()

r = 0
while Ss[-1] != END:
    r += Ts.pop()
    Ss.pop()
print(r)


Measured memory_bytes: 3060
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))

x = a.cumsum()
total_sum_a = a.sum()
y = total_sum_a - x

# print(a, total_sum_a, x, y, abs(x - y)[:-1])

print(min(abs(x - y)[:-1]))


Measured memory_bytes: 33080
s=str(input())
a=s[:2]
b=s[-2:]
m=['01','02','03','04','05','06','07','08','09','10','11','12']
if a not in m and b in m:
  print('YYMM')
elif a in m and b not in m:
  print('MMYY')
elif a in m and b in m:
  print('AMBIGUOUS')
else:
  print('NA')
  

Measured memory_bytes: 3060
a = [0]*5
for i in range(5):
  a[i] = int(input())

sorted_a = sorted(a,key = lambda x: (x - 1) % 10,reverse = True)
sum_time = 0
for i in range(5):
  while sum_time % 10 != 0:
    sum_time += 1
  sum_time += sorted_a[i]

print(sum_time) 

    

Measured memory_bytes: 2940
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int B[200010];
inline void add(int A) {
	while (A <= 200010) {
		B[A]++;
		A += A & -A;
	}
}

inline int query(int A) {
	int kotae = 0;
	while (A > 0) {
		kotae += B[A];
		A -= A & -A;
	}
	return kotae;
}

void pakuripair_sort(int N, ll A[], int B[]) {
	const int b = 9;
	ll tmp[200001];
	int tmp2[200001];
	rep(k, 6) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) {
			tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
			tmp2[kazu[A[i] >> k * b & ((1 << b) - 1)]] = B[i];
		}
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) {
			A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
			B[kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp2[i];
		}
	}
}

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);

	int N = getint();
	int K = getint();

	ll A[200001];
	A[0] = (ll)N * K;
	rep1(i, N) {
		B[i] = i;
		A[i] = A[i - 1] + getint() - K;
	}
	pakuripair_sort(N + 1, A, B);
	rep(i, N + 1) A[B[i]] = i + 1;
	memset(B, 0, sizeof(B));
	ll kotae = 0;
	rep(i, N + 1) {
		kotae += query(A[i]);
		add(A[i]);
	}
	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 4992
#include <stdio.h>
#include <stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left!=NIL) x=x->left;
  return x;
}

Node treeMaximum(Node x){
  while(x->right!=NIL) x=x->right;
  return x;
}

Node treeSearch(Node u, int k){
  while(u!=NIL && k !=u->key){
    if(k<u->key) u=u->left;
    else u=u->right;
  }
  return u;
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right!=NIL) return treeMinimum(x->right);
  y=x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted                                                           
  Node x; // child of y                                                                   

  if(z->left==NIL || z->right==NIL) y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL) x=y->left;
  else x=y->right;

  if(x!=NIL) x->parent=y->parent;

  if(y->parent==NIL) root=x;
  else {
    if(y==y->parent->left) y->parent->left=x;
    else y->parent->right=x;
  }
  if(y!=z) z->key=y->key;

  free(y);

}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if((z->key)<(x->key)) x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL) root=z;
  else {
    if((z->key)<(y->key)) y->left=z;
    else y->right=z;
  }
}

void inorder(Node u){

  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);

}
void preorder(Node u){

  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);

}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}




Measured memory_bytes: 25228
#include <iostream>
using namespace std;

int main() {
	int n, a[100000], b[100000];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		a[i] %= b[i];
	}
	int64_t m = 0;
	for (int i = n - 1; i >= 0; i--) {
		if ((a[i] + m) % b[i] != 0) {
			m += b[i] - (a[i] + m) % b[i];
		}
	}
	cout << m << endl;
	return 0;
}


Measured memory_bytes: 1152
#include <iostream>

using namespace std;

typedef long long int ll;

int main() {
    ll x;

    cin >> x;

    ll ans = 0;
    for (ll i = x; ; ) {
        if (i == 2) {
            ans = 2;
            break;
        }

        ll num = i;
        if (i % 2 == 0) {
            i += 1;
            continue;
        } else {
            i += 2;
        }

        bool flg = true;
        for (ll j = 3; j * j <= num; j+=2) {
            if (num % j == 0)  {
                flg = false;
                break;
            }
        }
        if (flg) {
            ans = num;
            break;
        }
    }
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,m;
  {
  cin >> n >> m;
    ll ans = 0,a;
    vary(ll,v,n+1,0);
    rep(i,n-1){
      cin >> a;
      v[i+1] = v[i]+ a;
    }
    ll dis = 0,p = 0;
    rep(i,m){
      cin >> a;
      dis += abs(v[p+a] - v[p]);
      dis %= 100000;
      p += a;
    }
    cout << dis << endl;
  }
  return 0;
}

Measured memory_bytes: 3600
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 998244353;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {   
    ll n, k; cin >> n >> k;
    vector<ll>A(n); rep(i, n) cin >> A[i];

    ll dp[60][2];
    rep(i, 60)rep(j, 2) dp[i][j] = -1;
    dp[0][0] = 0; //i桁目まで見たときのXORの合計の最大値, smaller

    int num =50;
    rep(i, num){
        ll mask = 1LL << (num - i - 1);
        ll cnt0 = 0, cnt1 = 0;
        int c = 0;
        rep(j, n) if(A[j] & mask)c++;
        cnt0 = mask * c;
        cnt1 = mask * (n - c);

        //smaller -> smaller
        if(dp[i][1] != -1){
            chmax(dp[i+1][1], dp[i][1] + max(cnt1, cnt0));
        }
        //exact -> smaller
        if(dp[i][0] != -1){
            if(k & mask){
                chmax(dp[i+1][1], dp[i][0] + cnt0);
            }
        }
        //exact -> exact
        if(dp[i][0] != -1){
            if(k & mask)chmax(dp[i+1][0], dp[i][0] + cnt1);
            else chmax(dp[i+1][0], dp[i][0] + cnt0);
        }
    }

    cout << max(dp[num][0], dp[num][1]) << ln;
}


Measured memory_bytes: 1024
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node {
  int p;
  int l;
  int r;
};//parent,left,right meaning

struct Node T[MAX];
int n,D[MAX],H[MAX];

void setDepth(int u,int d){
  if (u == NIL) return;
  D[u] = d;
  setDepth(T[u].l,d + 1);
  setDepth(T[u].r,d + 1);
}

int setHeight(int u){
  int h1 =0,h2 =0;
  if(T[u].l != NIL) h1 = setHeight(T[u].l) + 1;
  if(T[u].r != NIL) h2 = setHeight(T[u].r) + 1;
  return H[u] = (h1 > h2 ? h1 : h2);
}

//節点uの兄弟返す
int getSibling(int u){
  if(T[u].p == NIL )return NIL;
  if(T[T[u].p].l != u && T[T[u].p].l != NIL)
    return T[T[u].p].l;
  if(T[T[u].p].r != u && T[T[u].p].r != NIL)
    return T[T[u].p].r;
  return NIL;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ", T[u].p);
  printf("sibling = %d, ", getSibling(u));
  int deg = 0;
  if(T[u].l != NIL) deg++;
   if(T[u].r != NIL) deg++;
   printf("degree = %d, ", deg);
   printf("depth = %d, ", D[u]);
   printf("height = %d, ", H[u]);

   if(T[u].p == NIL){
     printf("root\n");
   }else if(T[u].l == NIL && T[u].r == NIL){
     printf("leaf\n");
   }else{
     printf("internal node\n");
   }
}

int main(){
  int v,l,r,i,root=0;
  scanf("%d",&n);

  for(i=0;i < n;i++) T[i].p = NIL;

  for(i=0; i < n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l = l;
    T[v].r = r;
    if(l != NIL) T[l].p = v;
    if(r != NIL) T[r].p = v;
  }

  for(i =0;i < n;i++) if(T[i].p == NIL) root = i;

  setDepth(root,0);
  setHeight(root);

  for(i =0;i < n;i++) print(i);

  return 0;
}



Measured memory_bytes: 2108
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#define lol(i,n) for(ll i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
ll gcd(ll x,ll y){
    if(x<y)swap(x,y);
    if(y==0)return x;
    return gcd(x%y,y);
}
#define N 100010
ll n;
bool win(ll a[]){
    if(n==1){
	if(a[0]==1)return 0;
	return 1;
    }
    ll cnt=0;
    lol(i,n)cnt+=(a[i]%2==0);
    if(cnt&1)return 1;
    if(cnt==n-1){
	lol(i,n)if(a[i]&1)a[i]--;
	lol(i,n)if(!a[i])return 0;
	ll g=a[0];
	for(ll i=1;i<n;i++){
	    g=gcd(g,a[i]);
	}
	lol(i,n)a[i]/=g;
	return 1 xor win(a);
    }
    return 0;
}
ll a[N];
int main(){
    cin>>n;
    lol(i,n)cin>>a[i];
    cout<<(win(a)?"First":"Second")<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
using namespace std;

int main() {
	int x = 0;
	int ans = 0;
	int n;
	string s;
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'I') x++;
		else x--;
		if (x >= ans) ans = x;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  int d;
  cin >> d;
  if(d == 25) cout << "Christmas\n";
  else if(d == 24) cout << "Christmas Eve\n";
  else if(d == 23) cout << "Christmas Eve Eve\n";
  else cout << "Christmas Eve Eve Eve\n";
}


Measured memory_bytes: 3568
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define str to_string
#define endl "\n"
#define PI 3.141592653589
using namespace std;
using lint = long long;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
const int mod=1000000007;
//AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    lint n,ans,e0=2,e09=1;cin>>n;
    if(n==1)ans=0;
    else if(n==2)ans=2;
    else{
        ans=1;
        for(int i=0;i<n;i++){
            ans*=10;ans%=mod;
        }
        for(int i=0;i<n;i++){
            e0*=9;e0%=mod;
        }
        for(int i=0;i<n;i++){
            e09*=8;e09%=mod;
        }
        ans=ans-e0+e09;
        ans%=mod;
        if(ans<0)ans+=mod;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;

int main() {
  int A,B,sum;
  cin >> A >>B;
  for(int i=0;i<2;i++){
    if(A>=B){
      sum+=A;
      A--;
    }
    else{
      sum+=B;
      B--;
    }
  }
  cout <<sum <<endl;
}

Measured memory_bytes: 256
x=int(input())
     
if 400 <= x <= 599:
  print(8)
elif 600 <= x <= 799:
  print(7)
elif 800 <= x <= 999:
  print(6)
elif 1000 <= x <= 1199:
  print(5)
elif 1200 <= x <= 1399:
  print(4)
elif 1400 <= x <= 1599:
  print(3)
elif 1600 <= x <= 1799:
  print(2)
elif 1800 <= x <= 1999:
  print(1)

Measured memory_bytes: 9192
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

struct UF {
	vector<int> data;
	UF(int size) : data(size, -1) { }
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool find(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

    int n,m;cin>>n>>m;
    UF uf(n+1);
    vector<int> p(n+1),rev(n+1);
    for(int i=1;i<=n;i++){
        cin>>p[i];
        rev[p[i]]=i;
    }
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        uf.unite(x,y);
    }
    int res=0;
    for(int i=1;i<=n;i++){
        int st=rev[i];
        if(uf.find(st,i)) res++;
    }
    cout<<res<<endl;
    
}


Measured memory_bytes: 1408
using System;

namespace _171_c
{
    internal class Dalmatians
    {
        private static void Main(string[] args)
        {
            var input = Console.ReadLine();
            if (input == null) return;
            var number = long.Parse(input);

            const int numOfAlphabet = 26;
            var result = GetName(number, numOfAlphabet);
            Console.WriteLine(result);
        }

        private static string GetName(long number, int numOfAlphabet)
        {
            var quotient = number / numOfAlphabet;
            var remainder = number % numOfAlphabet;

            // ちょうど割り切れた場合
            if (remainder == 0)
            {
                quotient -= 1;
                remainder = numOfAlphabet;
            }

            // 文字コードと数値の差分
            const int ascDiff = 96;

            if (quotient == 0)
            {
                return Convert.ToChar(remainder + ascDiff).ToString();
            }
            return GetName(quotient, numOfAlphabet) + Convert.ToChar(remainder + ascDiff);
        }
    }
}


Measured memory_bytes: 27464
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int n, m, q;
vector<int> a, b, c, d;
int ans;

void dfs(vector<int> A) {
    if (A.size() == n + 1) {
        // calculate score
        int temp_score = 0;
        for (int i = 0; i < q; i++) {
            if (A[b[i]] - A[a[i]] == c[i]) {
                temp_score += d[i];
            }
        }
        ans = max(ans, temp_score);
        return;
    }

    A.push_back(A.back());
    while (A.back() <= m) {
        dfs(A);
        A.back()++;
    }
}

int main() {
    cin >> n >> m >> q;

    a = vector<int>(q);
    b = vector<int>(q);
    c = vector<int>(q);
    d = vector<int>(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    dfs(vector<int>(1, 1));
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3636
H,W = map(int,input().split())
S = [list(input()) for i in range(H)] # S[i][j] i行j列
def judge(l,i,j):
    count = 0
    for a in [-1,0,1]:
        for b in [-1,0,1]:
            if a == 0 and b == 0:
                continue
            else:
                if (not 0 <= i+a <= H-1) or (not 0 <= j+b <= W-1):
                    continue
                elif S[i+a][j+b] == "#":
                    count += 1
    return count
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = judge(S,i,j)
        print(S[i][j],end = "")
    print("")

Measured memory_bytes: 3444
#include <bits/stdc++.h>

#define pp push_back
#define pf push_front
#define mp make_pair
#define fs first
#define sc second
#define sf scanf

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;

const int N = (int) 1e5;
const ll INF = (ll) 1e16 + 7;

int main(int argc, char *argv[])
{
	ll a, b, n;
	sf("%lld %lld %lld", &a, &b, &n);

	ll l = 0, r = n;
	ll ans = INT_MIN;
	while (l <= r) {
		ll mid = (l + r) / 2;
		ll x = a * mid / b - a * (mid / b);
		if (x >= ans) {
			ans = x;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}

	printf("%lld", ans);

	return 0;
}


Measured memory_bytes: 3848
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		//N回ループ、a,bについてt回目のループ（＝t秒後）について可能か調べる
		Scanner sc = new Scanner(System.in);
		//Nの入力
		int N =sc.nextInt();
		boolean result =true;
		for(int i=0;N>i;i++) {
		int t =sc.nextInt();
		int a =sc.nextInt();
		int b =sc.nextInt();
			if(!(t-a-b>=0 && (t-a-b)%2==0)) {
				result =false;
			}
		}
		if(result){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 87100
#include <stdio.h>
#include <string.h>

int main(void){

int n,i=0,j=0,count=0,check=1;
char str[50+1];
char abc[] = "ABC"; 

scanf("%d\n%s",&n,str);

while(i <(n-2)){
   while(j <3){
   //printf("%c,%c\n",str[j+i],abc[j]);
			if (str[j+i]!=abc[j]){
				check=0;
                   //printf("%d\n",check);
                goto OUT;
			}
            j++;
        }
                   //printf("%d\n",check);
   if (check==1){
   		count++;
   }
   OUT:
   j=0;
   check=1;
	i++;
}

printf("%d",count);

return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

int a[MAXN];
inline int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("a.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, k, i;
    cin >> n >> k;
    for(i = 0; i < n; i++){
        cin >> a[i];
    }
    if(n == 1){
        if(k == a[0]){
            cout << "POSSIBLE" << endl;
        }
        else cout << "IMPOSSIBLE" << endl;
    }
    else{
        int gcdv = gcd(a[0], a[1]);
        for(i = 2; i < n; i++){
            gcdv = gcd(gcdv, a[i]);
        }
        bool ans = false;
        for(i = 0; i < n; i++){
            if(a[i] >= k){
                if((a[i] - k) % gcdv == 0){
                    ans = true;
                }
            }
        }
        if(ans){
            cout << "POSSIBLE" << endl;
        }
        else cout << "IMPOSSIBLE" << endl;

    }




    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}



Measured memory_bytes: 640
#include <stdio.h>

int main(){
  int n;  scanf("%d", &n);
  int tmp, min, ans = 1;
  
  scanf("%d", &tmp);
  min = tmp;
  for(int i=1; i<n; i++){
    scanf("%d", &tmp);
    if(tmp <= min){
      ans++;
      min = tmp;
    }
  }

  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>
#include<list>

/*
　　　　　　　　　　　　　　　　　　　　　__,.二ﾆ==-　　ﾆ．、_.　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　.,.．‐　⌒　　　　　　　　　　　　｀`'ァ-ﾆ、.　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　ィ'´.　　　　　　　　　　　　　　　　　　　　　　´丶.、　　　　　　　　　　　　
　　　　　　　　　　　.,ィ'´　　　　　　　　　　　　　　　　　　　　　　　　　　　　`.ｘ、..　　　　　　　　　
　..　　　　　　　　／.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　､＼.　　　　　　　　
　　　　　　　　.ﾝ′.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　￢`""冖ｰミト．
　　　　　　　,ｒ′.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.ﾍ、　　　　`
　　　　　　ﾂ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　`、....　　　
　　　　　./´　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ﾍ　　　　
　.....　　/.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.〉.　　　
　　　´/..　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.ｌ　　　
　　　ｨ　　　　　　　　　　　　　　　　　　　　　　　　　．　　　　　　　　　　　　　　　　　　　　　ｆ..　　
　..　.ｆ　,d.　　　　　　　　　　　　　　　　　l　　　′　」　　,.　　　　　　　　　　　　　ﾄ　　　　　！　　
　.　〕../.ｆ..　　　　　　　　　　　　　　　　　′　．.　　|　　.｝　　　　　　　　　　　　　|　　　　　　|.　　
　　.!./..f..　　　　　　　　　　　　　　　　　/　　!－　ナ丶п冖т　　　　ﾉｰ-　．　〕　　　　　　|.　　
　　|ﾒ　|　　　　　　　　　　　　　　　｜　j　　　　　　,　　┌．　|〈.　　　л`.　　　/|..　　　　　┤,..　
　...「...｜.　　　　　　|　　´　　　　　　l.　|　　j.Ｌ......ｭ.Ｌ＿└ヽ_｜Y.　　ﾒムｗ　ょ　|　　j.:　　　|　￣
　.　　｜.　　　　　　　　　　　　　　　т〕＜.ィ冖T冖..　г‐　`､　`,　/┴￢..г￣|..　.′　　｜　　
　...　　|　　　　　　　　．..　　　　　　　),|..　｀　　ﾘ　「_ﾉ.||　　　　`　V　　|!｛,｢ll　´.」.　　　　　卜　　
　.　　｜.」　　　　　　′　　　　　　　　ヽ　　　　└++〃..　　　　　　　　ﾙｗｆ　　ｶz′.　　　｜.　　
　　　　|..〕　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　｢　　　　　．|　　　
　　　　.ｌ.|.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　′.　　　　　|　　　
　.　　　.〕..　　　　　　　　　　　　　　　`!　　　　　　　　_...．.ｰ：''　　　　　　　　　｣　´　　　　λ.　　
　　　　_｢.　　　　,　　　　　　　　　　　　┐_,、｀~‐''"´　　　　　　　　　　　　　　　　ィ　　　.､　ﾍ、　
　　　　ｆ　　　　　　:_＿..,二ュ．-i―'''^~´　　　　　　　　　　　　　　　　　　　　　　　､＼イ　ヘ．`ｘ
　.　　/　　　　　　｛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　j　　　　.~^
　　､/　　　　　　　'ｔ..　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　丿..　　　　　
　.../.　　　　　　　,x┐..　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　∠∫　　　　　
　:^.　　　　　　　/　　￣冖ー=zzｭ┌ｰ―--　　　∟,二...＿.　　　　　　　_,､．-ｰ.'l+~.　.l｀．　　　　
　.　　　　　　　У.　　　　　　　　　⌒冖‐-=．_..　l｢.｢　　　　　　´￣｣了　　.,､-''＾　　　〉　ヽ_　　　
　　　　　　　_/.　　　　　　　　　　　　　　　　　　￣~'.ー-=．、＿,..usｧ.ｰ''"　　　　　　｛　　　＼´　
　　　　　　_ヰl'￢―-　､_　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（　　　　.＼
*/

using namespace std;

using ll = long long int;
using ull = unsigned long long int;

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n,ll mod = MOD){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%mod;
        }
        x = (x*x)%mod;
        n >>= 1;
    }
    return ret;
}

ll mygcd(ll a,ll b){
    if(b == 0)return a;
    return mygcd(b,a%b);
}

ll twoPow(ll shiftNum){
    return (1LL << (shiftNum - 1));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    ll a;
    cin >> a;
    string str;
    cin >> str;

    ll b = (int)(str[0] - '0')*100 + (int)(str[2] - '0')*10 + (int)(str[3] - '0');
    cout << (a*b)/100 << endl;
    return 0;
}

Measured memory_bytes: 3652
// Copyright lzt
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<long long, long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i, j, k)  for (register int i = (int)(j); i <= (int)(k); i++)
#define rrep(i, j, k) for (register int i = (int)(j); i >= (int)(k); i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)

inline ll read() {
  ll x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    x = 10 * x + ch - '0';
    ch = getchar();
  }
  return x * f;
}

const int maxn = 1010;
int n;
struct lzt {
  int w, s, v;
  bool operator < (const lzt &b) const {
    return s < b.s;
  }
} a[maxn];
ll f[1010][20010];

void work() {
  n = read();
  rep(i, 1, n) {
    a[i].w = read();
    a[i].s = read();
    a[i].v = read();
    a[i].s += a[i].w;
  }
  sort(a + 1, a + n + 1);
  rep(i, 1, n) {
    rep(j, 0, a[i].s) {
      f[i][j] = f[i - 1][j];
      if (a[i].w <= j) f[i][j] = max(f[i][j], f[i - 1][j - a[i].w] + a[i].v);
    }
  }
  ll ans = 0;
  rep(i, 0, 20000) ans = max(ans, f[n][i]);
  cout<<ans<<endl;
}

int main() {
  #ifdef LZT
    freopen("in", "r", stdin);
  #endif

  work();

  #ifdef LZT
    Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
  #endif
}


Measured memory_bytes: 157824
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)



int main() {
    int a, b;
    cin >> a >> b;
    
    int ans = -1;
    
    rep(i,1300) {
        if(i * 8 / 100 == a && i * 10 / 100 == b) {
            ans = i;
            break;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}




Measured memory_bytes: 3636
import java.util.Scanner;

/**
 * B
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String Sa = sc.nextLine();
        String Sb = sc.nextLine();
        String Sc = sc.nextLine();

        char ch = Sa.charAt(0);
        int a = 1;
        int b = 0;
        int c = 0;
        String ans = "";
        while (true) {
            if (ch == 'a') {
                if (a == Sa.length()) {
                    ans = "A";
                    break;
                }
                ch = Sa.charAt(a);
                a++;
            } else if (ch == 'b') {
                if (b == Sb.length()) {
                    ans = "B";
                    break;
                }
                ch = Sb.charAt(b);
                b++;
            } else {
                if (c == Sc.length()) {
                    ans = "C";
                    break;
                }
                ch = Sc.charAt(c);
                c++;
            }
        }

        System.out.println(ans);
        sc.close();
    }
}

Measured memory_bytes: 23764
h, w = map(int, input().split(" "))
n = int(input())
a = list(map(int, input().split(" ")))

mat = [] * h

line = []
for i in range(n):
    for j in range(a[i]):
        line.append(i+1)
        if len(line) == w:
            if len(mat) % 2 == 0:
                mat.append(line)
            else:
                line.reverse()
                mat.append(line)
            line = []
                
for i in mat:
    print(' '.join(map(str, i)))



Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
cout<<fixed<<setprecision(10);

  char a,b;
  string s,t;
  cin >> a >> b;
  for (int i=0; i<b-'0';i++){
     s+=a;
  }
  for (int i=0; i<a-'0';i++){
    t+=b;
  }
  if (s>t) cout << t;
  else cout <<s;
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>

const int N=2005;

int n,m,a[N][N];

void solve(int x)
{
	if (x==1) {a[1][1]=1;return;}
	solve(x-1);
	int n=1<<(x-1);
	for (int i=1;i<n;i++)
		for (int j=1;j<n;j++)
			a[i+n][j]=a[i][j+n]=a[i+n][j+n]=a[i][j];
	a[n][n]=1;
}

int main()
{
	scanf("%d%d",&n,&m);
	solve(std::max(n,m));
	for (int i=1;i<(1<<n);i++)
	{
		for (int j=1;j<(1<<m);j++) putchar(a[i][j]+'0');
		puts("");
	}
	return 0;
}


Measured memory_bytes: 9472
<?php
    $fnum = trim(fgets(STDIN));
    $sline = trim(fgets(STDIN));
    $sarray = explode(' ',$sline);
    echo implode(' ', $sarray), PHP_EOL;
    insertion_sort($sarray, $fnum);
    
    function insertion_sort($array, $num) {
        for ($i = 1; $i <= $num - 1; $i++) {
            $v = $array[$i];
            $j = $i - 1;
            while ($j >= 0 && $array[$j] > $v) {
                $array[$j + 1] = $array[$j];
                $j--;
                $array[$j + 1] = $v;
            }
        echo implode(' ', $array), PHP_EOL;
        }
    }
    

Measured memory_bytes: 15492
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <functional>
#include <math.h> 
#define enld '\n'
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------



int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll K;
  cin >> K;
  if(K%2 == 0 || K%5 == 0){
    cout << -1 << "\n";
    return 0;
  }
  ll now = 1;
  ll rem = 0;
  int cnt = 0;
  while(1){
    cnt++;
    rem += now*7;
    rem %= K;
    if(rem == 0){
      cout << cnt << "\n";
      return 0;
    }
    now *= 10;
    now %= K;
  }
  return 0;
}

Measured memory_bytes: 3648
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <numeric>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define FOR(x, b, e) for(int x=(b); x<=(e); ++x)
#define FORD(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define REP(x, n) for(int x=0; x<(n); ++x)
#define ALL(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it) {
	*this << ((it != d.b) ? ", " : "") << *it;
  }
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

int main() {
	ios_base::sync_with_stdio(false);
	int n, r;
	cin >> n >> r;
	if (n >= 10) {
		cout << r << endl;
	} else {
		cout << r  + 100 * (10 - n) << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	int n, a, b, c;
	cin >> n >> a >> b >> c;
	vector<string> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	vector<char> res;
	for (int i = 0; i < n; i++) {
		string t = v[i];
		if (t == "AB") {
			if (a == 0 && b == 0) {
				break;
			}
			if (a == 1 && b == 1 && c == 0 && i < n-1) {
				if (v[i + 1] == "AC") {
					a++;
					b--;
					res.push_back('A');
				}
				else {
					a--;
					b++;
					res.push_back('B');
				}
			}
			else if (a <= b) {
				a++;
				b--;
				res.push_back('A');
			}
			else {
				a--;
				b++;
				res.push_back('B');
			}
		}
		else if (t == "AC") {
			if (a == 0 && c == 0) {
				break;
			}
			if (a == 1 && c == 1 && b == 0 && i < n - 1) {
				if (v[i + 1] == "AB") {
					a++;
					c--;
					res.push_back('A');
				}
				else {
					a--;
					c++;
					res.push_back('C');
				}
			}
			else if (a <= c) {
				a++;
				c--;
				res.push_back('A');
			}
			else {
				a--;
				c++;
				res.push_back('C');
			}
		}
		else {
			if (b == 0 && c == 0) {
				break;
			}
			if (b == 1 && c == 1 && a == 0 && i < n - 1) {
				if (v[i + 1] == "AB") {
					b++;
					c--;
					res.push_back('B');
				}
				else {
					b--;
					c++;
					res.push_back('C');
				}
			}
			else if (b <= c) {
				b++;
				c--;
				res.push_back('B');
			}
			else {
				b--;
				c++;
				res.push_back('C');
			}
		}
	}

	if (res.size() == n) {
		cout << "Yes" << endl;
		for (int i = 0; i < n; i++) {
			cout << res[i] << endl;
		}
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 6668
#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-8;

struct Point{
    double x, y, c;
};

vector<pair<double, double>> intersection(double x1, double y1, double r1, double x2, double y2, double r2){
    double ab = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

    if (-EPS < (r1 - r2) - ab || ab - (r1 + r2) > -EPS)
        return {};
    
    double ad = (r1 * r1 - r2 * r2 + ab * ab) / (2 * ab);
    double x0 = x1 + (x2 - x1) * ad / ab;
    double y0 = y1 + (y2 - y1) * ad / ab;
    double n_x = -(y2 - y1), n_y = x2 - x1;
    double norm = sqrt((n_x * n_x) + (n_y * n_y));
    double cd = sqrt((r1 * r1) - (ad * ad));

    return {{x0 + n_x * cd / norm, y0 + n_y * cd / norm}, {x0 - n_x * cd / norm, y0 - n_y * cd / norm}};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cout << fixed << setprecision(10);

    int n, k;
    cin >> n >> k;

    vector<Point> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i].x >> a[i].y >> a[i].c;

    auto C = [&](double mid){
        vector<double> r(n);
        for (int i = 0; i < n; i++)
            r[i] = mid / a[i].c;

        vector<pair<double, double>> center;
        for (int i = 0; i < n; i++){
            center.push_back({a[i].x, a[i].y});
            for (int j = i + 1; j < n; j++){
                auto v = intersection(a[i].x, a[i].y, r[i], a[j].x, a[j].y, r[j]);

                for (auto k: v)
                    center.push_back(k);
            }
        }
        
        for (auto c: center){
            int cnt = 0;
            for (auto i: a){
                if (mid - i.c * sqrt((c.first - i.x) * (c.first - i.x) + (c.second - i.y) * (c.second - i.y))  > -EPS)
                    cnt += 1;
            }

            if (cnt >= k)
                return true;
        }

        return false;

    };

    double lb = 0.0, ub = 1e9;
    for (int i = 0; i < 100; i++){
        double mid = (lb + ub) / 2;
        if (C(mid))
            ub = mid;
        else
            lb = mid;
    }

    cout << ub << '\n';
    
    return 0;
}


Measured memory_bytes: 384