akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    string S;
    cin>>S;
    int ans=0;
    for (size_t i = 0; i < S.size(); i++)
    {
        if(S[i]=='+')
        ans++;
        else
        ans--;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!

#N,K = list(map(int, input().split()))
#return chr(64+num)
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0 for i in range(Q)]
C = [0 for i in range(Q)]
for i in range(Q):
    B[i], C[i] = list(map(int, input().split()))

dic = Counter(A)

ans = 0
for i in range(max(A)+1):
    ans += i * dic[i]
for i in range(Q):
    ans += dic[B[i]] * (C[i]-B[i])
    print(ans)
    dic[C[i]] += dic[B[i]]
    dic[B[i]] = 0



Measured memory_bytes: 30124
#include <iostream>

int main(){
	int n;
	int a[100005] = {0}, b[100005] = {0}, c[100005] = {0};
	int d[100005][3] = {0};
	std::cin >> n;
	for(int i = 1; i <= n; i++){
		std::cin >> a[i] >> b[i] >> c[i];
		
		d[i][0] = std::max(d[i - 1][1], d[i - 1][2]) + a[i];
		d[i][1] = std::max(d[i - 1][0], d[i - 1][2]) + b[i];
		d[i][2] = std::max(d[i - 1][1], d[i - 1][0]) + c[i];
	}
	
	std::cout << std::max(d[n][0], std::max(d[n][1], d[n][2])) << '\n';
	return 0;
}


Measured memory_bytes: 5944
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	string s,t;
	cin >> s >> t;
	cout << (s[0] == t[0]) + (s[1] == t[1]) + (s[2] == t[2]) << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
class Main
{
	public static void main(String args[]) throws IOException
	{
		try{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String arr[]=br.readLine().split(" ");
		float a=0;float b=0;float c=0;
		float ti=0;
		a=Float.parseFloat(arr[0]);
		b=Float.parseFloat(arr[1]);
		c=Float.parseFloat(arr[2]);
		ti=a/c;
		//System.out.println(ti);
		if(ti<=b)
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
	}
	catch(Exception e){}
}}

Measured memory_bytes: 33056
#include <bits/stdc++.h>
using namespace std;
long long A,B,N;
int main()
{
	cin>>N>>A>>B;
	long long Ans=0;
	long long v=N/(A+B);
	N%=(A+B);
	Ans=min(A,N);
	Ans+=v*A;
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define INF 1e+18
#define int long long
using namespace std;

signed main(){
	int n,s,mi = INF;
	cin >> n >> s;
	if(n == s) mi = n + 1;
	for(int i = 2;i * i <= n;i++){
		int sum = 0,tmp = n;
		while(tmp){
			sum += tmp % i;
			tmp /= i;
		}
		if(sum == s) mi = min(mi,i);
	}
	if(n - s >= 1){
		for(int i = 1;i * i <= n - s;i++){
			if((n - s) % i == 0){
				int b = (n - s) / i + 1;
				if(i < b && s - i < b && s - i >= 0) mi = min(mi,b);
			}
		}
	}
	if(mi == INF) cout << -1 << endl;
	else cout << mi << endl;
	return 0;
}

Measured memory_bytes: 256
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####

def solve(K, A, B):
    q,r = divmod(A, K)
    q += r> 0
    q *= K
    return A <= q <= B

K = rri()
A, B = rrm()
ans = solve(K, A, B)
print "OK" if ans else "NG"


Measured memory_bytes: 64176
#include <iostream>
#include <iomanip>
#include <cassert>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <sstream>
#include <istream>
#include <cmath>
#include <cstdio>

using namespace std;

#define vci vector<int>
#define vcs vector<string>
#define pb push_back
#define sz size()
#define mapii map<int, int>
#define mapci map<char, int>
#define mapsi map<string, int>
#define all(x) x.begin(), x.end()
#define minit(a, i) memset(a, i, sizeof(a));

#define for_(i, a, b) for (int i=(int)a; i<(int)b; i++)
#define for_d(i, a, b) for (int i=(int)a-1; i>=b; i--)
#define for_r(i, a, b, c) for (int i=(int)a; i<(int)b; i += c)
#define for_dr(i, a, b, c) for (int i=(int)a-1; i>=b; i -= c)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

typedef long long ll;
typedef double D;

const int iINF = 2147483647;
const ll lINF = 9223372036854775807;

template <class T> inline void dbg(T t) { cout << t << endl; }




int main() {
	string in;
	mapsi res;
	while (cin>>in) { 
		in = in.substr(in.find(',')+1);
		res[in]++;
	}
	cout << res["A"] << endl;
	cout << res["B"] << endl;
	cout << res["AB"] << endl;
	cout << res["O"] << endl;
	return 0;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define srt(i) sort(i.begin(), i.end())
#define rvt(i) sort(i.begin(), i.end(), greater<int>())

char itoc(int i){
  string s = "zabcdefghijklmnopqrstuvwxy";
  return s.at(i);
}

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

    int ac=0,wa=0,tle=0,re=0;
    rep(i,n){
      string s;
      cin >> s;

      if(s=="AC") ac++;
      else if(s=="WA") wa++;
      else if(s=="TLE") tle++;
      else if(s=="RE") re++; 
    }
    
    cout << "AC x " + to_string(ac) << endl;
    cout << "WA x " + to_string(wa) << endl;
    cout << "TLE x " + to_string(tle) << endl;
    cout << "RE x " + to_string(re) << endl;
}


Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef pair<double,double> PD;
typedef pair<int,P> ed;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  vp ab(N);
  bool eq=true;
  int minb=INF;
  ll suma = 0;
  rep(i,N) {
    cin >> ab[i].first >> ab[i].second;
    eq &= ab[i].first == ab[i].second;
    if(ab[i].first > ab[i].second) {
      chmin(minb,ab[i].second);
    }
    suma += ab[i].first;
  }
  if(eq) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = suma-minb;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define repeat(i,a,b) for(int i=(a),i##__end=(b);i<i##__end;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,i##__end=(a);i>=i##__end;i--)
#define mst(a,x) memset((a),(x),sizeof(a))
#define pii pair<int,int>
ll n,m,l,a[310][310],b[310][310];
ll x,y,z;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m>>l;
	repeat(i,0,n)
	repeat(j,0,n)
		a[i][j]=b[i][j]=(i==j?0ll:1ll<<60);
	repeat(i,0,m){
		cin>>x>>y>>z;x--,y--;
		a[x][y]=z;
		a[y][x]=z;
	}
	repeat(k,0,n)
	repeat(i,0,n)
	repeat(j,0,n)
		a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	repeat(i,0,n)
	repeat(j,i+1,n)
	if(i!=j && a[i][j]<=l){
		b[i][j]=1;
		b[j][i]=1;
	}
	repeat(k,0,n)
	repeat(i,0,n)
	repeat(j,0,n)
		b[i][j]=min(b[i][j],b[i][k]+b[k][j]);
	int q;cin>>q;
	while(q--){
		cin>>x>>y;x--,y--;
		cout<<(b[x][y]>10000?0:b[x][y])-1<<endl;
	}
	return 0;
}


Measured memory_bytes: 2048
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
table = [False for i in range(N+1)]
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**(0.5)+1)):
        if not is_prime[i]:
            continue
        for j in range(i*2,n+1,i):
            is_prime[j] = False
    return is_prime
p = primes(N)
pr = []
for i in range(N+1):
    if p[i]:
        pr.append(i)
n = len(pr)
ans = 1
def dfs(cur_num,index,s,pre,me):
    global ans
    for i in range(index,n):
        if i == index:
            if cur_num*pr[i] <= N:
                ans += (pre*(me+2))*cur_num*pr[i]
                dfs(cur_num*pr[i],index,s+pre*(me+2),pre,me+1)
            else:
                break
        else:
            if cur_num*pr[i] <= N:
                ans += pre*(me+1)*2*cur_num*pr[i]
                dfs(cur_num*pr[i],i,s+pre*(me+1)*2,pre*(me+1),1)
            else:
                break
    return
dfs(1,0,1,1,0)
print(ans)

            
    


Measured memory_bytes: 356748
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())

#define pb emplace_back
#define fi first
#define se second
using ll = long long;
using P = pair<ll ,ll>;
//using Tu = tuple<ll, ll, ll>;
const ll INF = 1LL<<61LL;
const ll MOD = 1e9+7;



using ld = long double;

template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> void UNIQUE(vector<T> &a){ a.erase(unique(a.begin(), a.end()), a.end()); }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll in(){long long int x; assert(scanf("%lld", &x) == 1); return x;}
ld fin(){double x; assert(scanf("%lf", &x) == 1); return x;}
char yuyushiki[1000010]; string stin(){assert(scanf("%s", yuyushiki) == 1); return yuyushiki;}

int main(){
  ll N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  if(A > B)
    swap(A, B);
  ll rest = N-1;
  ll R = 0, L = 0;
  R = (B - A) / C;
  if(R > rest)
    R = rest;
  else{
    rest -= R;
    R += rest / 2;
    L += (rest + 1) / 2;
  }
  bool ans = false;
  assert(B - A >= (R - L) * C);
  //cout << L << "L R" << R << endl;
  if(B - A - (R - L) * C <= R * (D - C))
    ans = true;
  //if(ans)
  //  cout << "ya" << endl;
  while(B - A > (R - L) * C){
    R++;
    L--;
  }
  assert(B - A <= (R - L) * C);
  if(B - A  - (R - L) * C >= - L * (D - C))
    ans = true;
  if(ans)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


Measured memory_bytes: 256
/*
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
*/
#include <bits/stdc++.h>
#define pb push_back
#define FOR(x,st,n) for(int x = (st); x < (n); ++ x)

using namespace std;


typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vp;
typedef vector<int> vi;
typedef vector<vi> vvi;


int main(){
    
    ll a,b,k;
    cin>>a>>b>>k;
    
    ll ret;
    if(k< a){
        cout<< a-k <<" "<<b<<endl;
    }else{
        ret= b - (k-a );
        if(ret<0) ret=0;
        cout<<0<<" "<< ret<<endl;
    }
    

    return 0;
}



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

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

    string s;
    cin >> s;

    int n = s.size();

    bool f = true;
    for(int i = 0; i < n / 2; i++){
        if(s[i] == s[n - i - 1]);
        else{
            f = false;
            break;
        }
    }

    if(!f){
        cout << "No" << endl;
        return 0;
    }

    int idx = (n - 1) / 2 - 1;
    for(int i = 0; i < (n - 1) / 2; i++){
        if(s[i] == s[idx]);
        else{
            f = false;
            break;
        }
        idx--;
        if(i == (n - 1) / 4){
            break;
        }
    }

    if(!f){
        cout << "No" << endl;
        return 0;
    }

    reverse(s.begin(), s.end());

    idx = (n - 1) / 2 - 1;
    for(int i = 0; i < (n - 1) / 2; i++){
        if(s[i] == s[idx]);
        else{
            f = false;
            break;
        }
        idx--;
        if(i == (n - 1) / 4){
            break;
        }
    }

    if(!f){
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
ans = 0
L = 1
def lcm(x,y):
    return x//gcd(x,y)*y
for a in A:
    newL = lcm(L,a)
    ans = ans*(newL//L) + newL//a
    L = newL
print(ans%(10**9+7))

Measured memory_bytes: 70872
H, W = map(int, input().split())
A = []
for _ in range(H): A.append((input().strip()))
for h in range(H):
	for w in range(W):
		if A[h][w]=='c':
			tmp = 0
		elif A[h][0:w].count('c')==0:
			tmp = -1
		else:
			tmp = w-A[h][0:w].rindex('c')
		if w == W-1:
			print(tmp)
		else:
			print(tmp, end=' ')



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

int a[10][10];

void drop( int x, int y ){
  if( x<0 || x>=10 ) return;
  if( y<0 || y>=10 ) return;
  a[y][x]++;
}

int main(){
  int x,y,s;
  char c;

  for( int i=0;i<10;i++ )
    for( int j=0;j<10;j++ )
      a[i][j] = 0;

  while( cin>>x>>c>>y>>c>>s ){
    //    cout << x << " "<< y << " "<<s << endl;

    if( s>=1 ){
      drop(x,y);
      drop(x+1,y); drop(x-1,y);
      drop(x,y+1); drop(x,y-1);
    }
    if( s>=2 ){
      drop(x+1,y+1); drop(x+1,y-1);
      drop(x-1,y+1); drop(x-1,y-1);
    }
    if( s>=3 ){
      drop(x,y+2); drop(x,y-2);
      drop(x+2,y); drop(x-2,y);
    }
  }
  int zero=0;
  int mx=0;
  for( int i=0;i<10;i++ ){
    for( int j=0;j<10;j++ ){
      if( a[i][j]==0 ) zero++;
      if( a[i][j]>mx ) mx=a[i][j];
    }
  }
  cout << zero << endl;
  cout << mx << endl;

  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<string>
#include<numeric>
#include<set>
using namespace std;

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

  int k, a;
  vector<int> like(m, 0);

  for(int i = 0; i < n; i++){
    cin >> k;
    for(int j = 0; j < k; j++){
      cin >> a;
      like[a-1]++;
    }
  }

  int cnt = 0;

  for(int i = 0; i < m; i++){
    if(like[i] == n) cnt++;
  }

  cout << cnt << endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static BufferedReader reader;
	//static field here
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		reader = new BufferedReader(new InputStreamReader(System.in));
		//code here
		String[] ND = readLine();
		int N = Integer.parseInt(ND[0]);
		StringBuilder sb = new StringBuilder();
		String[] ss = readLine();
		for(int i=0;i<N;i++) {
			sb.append(ss[0].charAt(i));
			sb.append(ss[1].charAt(i));
		}
		
		//String[] s = readLine();
		print(sb.toString());
	}
	
	//functions here
	//note that all methods should be STATIC
	private static double getDistance(int[] p1,int[] p2) {
		double s = 0;
		for(int i=0;i<p1.length;i++) {
			s+=(p1[i]-p2[i])*(p1[i]-p2[i]);
		}
		return Math.sqrt(s);
	}
	
	private static String[] readLine(){
		try{
			return reader.readLine().split(" ");
		}catch(Exception e){
			e.printStackTrace();
			return new String[]{e.getMessage()};
		}
	}
	private static void print(Object o){
		System.out.println(o);
	}
	private static void print(){
		System.out.println();
	}
}

Measured memory_bytes: 21076
def main():
    Rec = 0
    Dia = 0
    while True:
        try:
            a,b,c = map(int,input().split(","))
            if a == b:
                Dia += 1
            elif a**2 + b**2 == c**2:
                Rec += 1
        except EOFError:
            break
    print('{}\n{}'.format(Rec,Dia))

if __name__ == '__main__':
    main()


Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
typedef vector<ll> vl;
typedef vector<vector<ll>> matrix;//matrix A(n, vl(m)); //n*m行列
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sortup(V) sort(V.begin(), V.end())
#define sortdown(V) sort(V.rbegin(), V.rend())
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(b<a){a=b;return 1;}return 0;}
#define MOD 1000000007 //998244353


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

    // solution comes here

    ll N;
    cin >> N;
    vl h(N);
    rep(i, N) cin >> h[i];

    vl dp(N);
    dp[1] = abs(h[0]-h[1]);
    for(ll i=2; i<N; i++) {
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
    }

    cout << dp[N-1] << nl;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<cmath>
 
#define rep(i,x) for(int i=0;i<(int)(x);i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)
 
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 2e9
#define MOD 1000000007
 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef std::pair<ll, ll> P;
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}

typedef std::pair<ll, ll> P;

bool pairCompare(const P& firstElof, const P& secondElof)
{
    return firstElof.second < secondElof.second;
}
 
using namespace std;

int main()
{
    ll n;
    cin >> n;
    vector<ll> b(n-1);
    vector<ll> a(n);

    rep(i, n-1) cin >> b[i];

    a[0] = b[0];
    a[n-1] = b[n-2];

    rep(i, n-2){
        a[i+1] = min(b[i], b[i+1]);
    }

    ll ans = 0;

    rep(i, n){
        ans += a[i];
    }

    cout << ans;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n,y;
	cin >> n >> y;

	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			int k = n-i-j;
			if(k>= 0 && i*10000+j*5000+k*1000 == y){
				cout << i << " " << j << " " << k << endl;
				return 0;
			}
		}
	}

	cout << -1 << " " << -1 << " " << -1 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
int main(){
//  freopen("test.in","r",stdin);
//  freopen("test.out","w",stdout);
	int n,count=0;
	cin>>n;
	char a[n+1];
	cin>>a;
	for(int i =0;i<n;i++){
		if(a[i]==a[i+1]) continue;
		else count++;
		
	} 
	cout<<count;
    return 0;
}


Measured memory_bytes: 384
var c,n,i:Longint;s:String;
begin
	readln(s);
	n:=length(s);
	for i:=2 to n do begin
		if s[i]<'a' then begin
			if s[i]='C' then inc(c) else inc(c,2);
		end;
	end;
	if (s[1]<>'A') or (c<>1) or (s[2]<'a') or (s[n]<'a') then writeln('WA')else writeln('AC');
end.


Measured memory_bytes: 128
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------        ]
    md = [list(map(int,input().split())) for i in range(2)]
    if md[0][0] == md[1][0]:
        print(0)
    else:
        print(1)

if __name__ == "__main__":
    main() #endline===============================================
    

Measured memory_bytes: 5684
def prm(x):
  if x == 1 or x == 4:
    return False
  for i in range(2,int(x**0.5+1)):
    if x%i == 0:
      return False
  return True
X=int(input())
for i in range(X,X**2):
  if prm(i):
    print(i)
    break

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define fto(i, a, b) for (int i = a; i <= b; i++)
#define fdto(i, a, b) for (int i = a; i >= b; i--)
#define fi first
#define se second
#define NTLiinhh "bai2"
const int maxn = 1e6+2, base = 1e9 + 7;
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int n, a[maxn];
long long k;
void Input()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    //freopen(NTLiinhh".inp", "r", stdin);
    //freopen(NTLiinhh".out", "w", stdout);
    cin >> n >> k;
    fto (i, 1, n) cin >> a[i];
}
int bit[maxn];
int get (int x)
{
    int s=0;
    while (x<maxn) {
        s+=bit[x];
        x+=x&(-x);
    }
    return s;
}
void update (int x)
{
    while (x>0) {
        bit[x]++;
        x-=(x&-x);
    }
}
void Solve()
{
    fto (i, 1, k-1)
        fto (j, 1, n) a[i*n+j]=a[j];
    n*=k;
    int res=0;
    fto (i, 1, n) {
        res+=get(a[i]+1);
        update (a[i]);
    }
    cout << res << endl;
}

void Solve2()
{
    long long res=0, s=((k-1)*k/2)%base;
    fto (i, 1, n) {
        long long sl=0;
        fto (j, 1, n) if (a[i] < a[j]) ++sl;
        res=(res+sl*s)%base;
        sl=0;
        fto (j, 1, i-1) if (a[i] < a[j]) ++sl;
        res=(res+sl*k)%base;
    }
    cout << res << endl;
}
int main()
{
    Input();
    if (n*k<=1000000) Solve(); else Solve2();
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
#define ll long long
#define vl vector
#define pb push_back
#define ff first
#define ss second
using namespace std;

int main()
{
    ll a,b,i,j,n,m,k,t;
    cin>>n;
    vl<pair<ll,ll>> v;
    for(i=0;i<n;i++)
    {
        cin>>a;
        v.pb({a,i+1});
    }
    sort(v.begin(),v.end());
    for(i=0;i<n;i++) cout<<v[i].ss<<" ";
}

Measured memory_bytes: 5360
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct edge{
	int v,nxt;
}g[N<<1];
int tot=0,head[N];
inline void add(int u,int v){
	g[++tot]=edge{v,head[u]}; head[u]=tot;
	g[++tot]=edge{u,head[v]}; head[v]=tot;
}
int n,m,dgr[N][2],q[N],h,t,vis[N];
char s[N];
int main(){
	scanf("%d%d%s",&n,&m,s);
	for(int i=1; i<=m; ++i){
		int u,v; scanf("%d%d",&u,&v);
		add(u,v); dgr[u][s[v-1]=='B']++; dgr[v][s[u-1]=='B']++;
	}
	h=t=0; for(int i=1; i<=n; ++i)if(!dgr[i][0]||!dgr[i][1])q[++t]=i,vis[i]=1;
	while(h<t){
		int u=q[++h];
		for(int i=head[u]; i; i=g[i].nxt){
			int v=g[i].v; if(vis[v])continue;
			--dgr[v][s[u-1]=='B'];
			if(!dgr[v][s[u-1]=='B']){
				vis[v]=1; q[++t]=v;
			}
		}
	}
	puts(t==n?"No":"Yes");
	return 0;
}

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

using namespace std;

int main()
{
    int a, b;
    char ch[15];
    scanf("%d %d", &a, &b);
    scanf("%s", ch);
    if(ch[a] != '-') printf("No\n");
    else{
        bool f = 1;
        for(int i = 0; i < (a + b + 1); ){
            if(i == a){
                i++;
            }
            else if(ch[i] >= '0' && ch[i] <= '9'){
                i++;
            }
            else{
                f = 0;
                break;
            }
        }
        printf("%s\n", f ? "Yes" : "No");
    }

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<double> v(n);
  for (int i = 0; i< n; i++) {
    cin >> v.at(i);
  }
  for (int i = 0; i < n-1; i++) {
    sort(v.begin(), v.end());
    v.at(i+1) = (v.at(i) + v.at(i+1) ) / 2;
    v.at(i) = 0;
  }
  cout << setprecision(7) << v.at(n-1) <<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[250],ans=0;
	cin>>n;
	for (int i=1;i<=n*2;i++)
	  cin>>a[i];
	sort(a+1,a+n*2+1);
	for (int i=1;i<=n*2;i+=2)
	  ans+=a[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  char s;
  cin >> s;
  if(s == 'a' || s == 'i' || s == 'u' || s == 'e' || s == 'o') {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <cstdlib>
typedef long long int ll;
using namespace std;

static long gcd(long a, long b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

long long int facctorialMethod(int k){//階乗
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

long long int tousasum(long long int n){//等差数列
    return n*(n+1)/2;
}

unsigned GetDigit(unsigned num){//桁数
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

bool IsPrime(int num)//素数判定
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

map< ll, ll > prime_factor(ll n) {//素因数分解
    map< ll, ll > ret;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n] = 1;
    return ret;
}

ll calcNumOfCombination(ll n, ll r){
    ll num = 1;
    for(ll i = 1; i <= r; i++){
        num = num * (n - i + 1) / i;
    }
    return num;
}



int main() {
    double W,H,x,y;
    cin >> W >> H >> x >> y;
    double result = W*H/2.0;
    printf("%lf\n",result);
    if(W/2.0==x&&H/2.0==y){
        cout << 1 << endl;
    }else{
        cout << 0 << endl;
    }

}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
H = LIST()

H = [-INF] + H

ma = 0
ma2 = 0
for i in reversed(range(1, N + 1)):
	if H[i] <= H[i - 1]:
		flag = True
	else:
		flag = False
		ma = 0
	if flag:
		ma += 1
		if ma2 < ma:
			ma2 = ma

print(ma2)

Measured memory_bytes: 16408
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define forn(i,a,b) for(long long i=a;i<b;i++)
#define ft first
#define sd second
#define sz size()
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
//cout << fixed << setprecision(12) <<x<<endl;

int main(){
fastIO;
#ifdef LOCAL
     freopen("in.txt", "r", stdin);
#endif

string s;cin>>s;
ll q;cin>>q;
deque<char> bc;
for(ll i=0;i<(ll)s.sz;i++){
    bc.push_back(s[i]);
}

int c=0;
bool flag=0;

while(q--){
    int opc;cin>>opc;
    if(opc==1){
        //reverse(all(bc));
       //c++;
       flag = !flag;
    }
    if(opc==2){
        int op;
        char a;
        cin>>op;
        cin>>a;
        if(flag){
            if(op==1){
                op++;
            }else{
                op--;
            }
        }
        if(op==1){
            //inicio
            bc.pf(a);
        }else{
            //final
            bc.pb(a);
        }
    }

}

/*for(auto &x:bc){
    cout<<x;
}*/
if(flag){
    for(int i=bc.sz-1;i>=0;i--){
        cout<<bc[i];
    }
    cout<<endl;
}else{
    for(auto &x:bc){
        cout<<x;
    }
    cout<<endl;
}
}



Measured memory_bytes: 4024
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<map>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;


long long int gcd(long long int a, long long int b)
{
	if (b == 0)
		return a;
	return gcd(b, a % b);
}




int main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	long long int n;
	cin >> n;
	long long int arr[n];
	for (long long int i = 0; i < n; i++)
		cin >> arr[i];
	long long int ans = 0;
	long long int maxi = arr[0];
	for (long long int i = 1; i < n; i++)
	{
		if (arr[i] < maxi)
		{
			ans += maxi - arr[i];
		}
		else {
			maxi = arr[i];
		}

	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5192
#include <iostream>
#include <numeric>

int main(){
    int n;
    std::cin >> n;

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int a;
        std::cin >> a;
        ans = std::gcd(ans, a);
    }
    
    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 3600
import bisect
a, b, q = map(int, input().split())
inf = 10**18
s = [-inf] + [int(input()) for i in range(a)] + [inf]
t = [-inf] + [int(input()) for i in range(b)] + [inf]

for i in range(q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = inf
  for S in [s[b-1], s[b]]:
    for T in [t[d-1], t[d]]:
      d1, d2 = abs(S-x) + abs(T-S), abs(T-x) + abs(S-T)
      res = min(d1, d2, res)
  print(res)


Measured memory_bytes: 78424
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

const int N=2e4+5;

ll a[N],b[N],dp[N];

int main()
{ios_base::sync_with_stdio(false);
int h,n;
cin>>h>>n;
rep(i,0,n-1)cin>>a[i]>>b[i];
rep(i,0,N-1)dp[i]=1e9+7;
dp[0]=0;
priority_queue<pair<ll,int> > q;
q.push(mp(0,0));
while(!q.empty())
{
	pair<ll,int> p=q.top();
	q.pop();
	ll d=-p.ff;
	int at=p.ss;
	if(d!=dp[at])continue;
	rep(i,0,n-1)
	{
		int to=at+a[i];
		to=min(to,h);
		if(dp[at]+b[i]<dp[to])
		{
			dp[to]=dp[at]+b[i];
			q.push(mp(-dp[to],to));
		}
	}
}
ol(dp[h]);
return 0;
}



Measured memory_bytes: 8812
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define endl '\n'
#define pb push_back
#define mod 1000000007
#define mp make_pair
#define pi acos(-1)
#define line cout<<"----------------------------"<<endl
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define filein freopen("input.txt","r",stdin)
#define fileout freopen("output.txt","w",stdout)
using namespace std;
const ll mx=3009;
int dp[mx][mx]; 
int main()
{
    string a,b; 
    cin>>a>>b;
    for(int i=(int)a.size()-1;i>=0;i--)
    {
	for(int j=(int)b.size()-1;j>=0;j--)
	{
	    if(a[i]==b[j]) dp[i][j]=1+dp[i+1][j+1]; 
	    else dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
	}
    }
    int i=0,j=0; 
    while(i<(int)a.size() and j<(int)b.size())
    {
	if(a[i]==b[j]) 
	{
	    cout<<a[i]; 
	    i++; j++; 
	}
	else
	{
	    if(dp[i+1][j]>dp[i][j+1]) i++; 
	    else j++; 
	}
    }
    cout<<endl; 

}



Measured memory_bytes: 35584
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Feb 26 17:52:43 2019

@author: nakamuratakayuki
"""

N, M, C = tuple(map(int, input().split()))
B_list = list(map(int, input().split()))
B_list.insert(0, 0)
A_list = [0]
for i in range(N):
    A_list.append(list(map(int, input().split())))
c = 0

for i in range(1,N+1):
    d = 0
    for j in range(1,M+1):
        d += A_list[i][j-1]*B_list[j]
    d += C
    if 0 < d:
        c += 1

print(c)

Measured memory_bytes: 3064
/*
 * cpp_filepath
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
void solve();
int main() { solve(); return 0; }

#include <set>
void solve() {
  int n;
  cin >> n;
  cout << 3 * n * n << endl;
}


Measured memory_bytes: 256
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = [i for i in input()]

if N[-1] in ['2','4','5','7','9']:
  print('hon')
elif N[-1] in ['0','1','6','8']:
  print('pon')
elif N[-1] in ['3']:
  print('bon')

Measured memory_bytes: 27096
#include<stdio.h>
int main(void)
{
	int n,sum,aum,k,i,j,x,box;
	int a[100];
	scanf("%d",&n);
	sum=0;
	aum=0;
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(i=0;i<n;i++){
		for(j=i+1;j<n;j++){
			if(a[i]<a[j]){
			box=a[i];
			a[i]=a[j];
			a[j]=box;
			}
		}
	}
	for(i=0;i<n;i++){
		if(i%2==0 || i==0){
			sum=sum+a[i];
		}
		if(!(i%2==0)){
			aum=aum+a[i];
		}
	if(aum>=sum){
		x=aum-sum;
	}
	if(aum<=sum){
		x=sum-aum;
	}
	}
	printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(){
	long int a,b,c,k;
  scanf("%ld %ld %ld %ld",&a,&b,&c,&k);
  if(a>k){
    printf("%ld",k);
    return 0;
  }
  else if(a+b>=k){
    printf("%ld",a);
    return 0;
  }
  else
    printf("%ld",a+(k-(a+b))*(-1));
}

Measured memory_bytes: 1732
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        int x, y;
        Scanner sc = new Scanner(System.in);
        x = sc.nextInt();
        y = sc.nextInt();
        System.out.println(CalculateGCD(x, y));
        sc.close();
    }

    public static int CalculateGCD(int x, int y) {
        if (x < y) {
            int temp;
            temp = x;
            x = y;
            y = temp;
        }
        if (x % y == 0) {
            return y;
        } else {
            return CalculateGCD(y, x % y);
        }
    }
}


Measured memory_bytes: 26384
#include <bits/stdc++.h>
  #define endl "\n"
  #define ll long long int
  #define vi vector<int>
  #define vll vector<ll>
  #define vvi vector < vi >
  #define pii pair<int,int>
  #define pll pair<long long, long long>
  #define mod 1000000007
  #define inf 1000000000000000001;
  #define all(c) c.begin(),c.end()
  #define mp(x,y) make_pair(x,y)
  #define mem(a,val) memset(a,val,sizeof(a))
  #define pb push_back
  #define f first
  #define se second
  
  using namespace std;
  int main()
  {
    std::ios::sync_with_stdio(false);
    ll n,W,ans=0;

    cin>>n>>W;
    ll dp[n+1][W+1]; mem(dp,0);
    ll v[n+1],w[n+1]; mem(v,0); mem(w,0);

    for (ll i = 1; i < n+1; ++i){
      cin>>w[i]>>v[i];
    }

    dp[1][0]=0;
    dp[1][w[1]]=v[1];

    for (ll i = 2; i < n+1; ++i)
    {
      dp[i][0]=0;

      for (ll j = 1; j < W+1; ++j)
      {
        dp[i][j]=dp[i-1][j];

        if(j-w[i]>=1)
          dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
      }
    }

    for (ll i = 1; i < W+1; ++i)
    {
      ans=max(ans,dp[n][i]);
    }

    cout<<ans;

    return 0;
  }

Measured memory_bytes: 82392
#include <stdio.h>
#include <math.h>
int main(void){
	int i,j,n,x[101],y[101];
	double sum,max;

	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&x[i]);
	for(i=0;i<n;i++)
		scanf("%d",&y[i]);
	for(j=1;j<=3;j++){
		sum = 0.0;
		for(i=0;i<n;i++){
			sum += pow(max=(abs(x[i]-y[i])),j);
		}
		sum = pow(sum,1.0/j);
		printf("%f\n",sum);
	}
	sum = abs(x[0]-y[0]);
	for(i=1;i<n;i++){
		if(abs(x[i]-y[i]) > sum)
			sum = abs(x[i]-y[i]);}		
	printf("%f\n",sum);

	return 0;
}
		

Measured memory_bytes: 696
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

const long long INFLL = 1LL << 60;
const int INFI = 1000000000;


int main(){
    string w; cin >> w;
    sort(w.begin(),w.end());
    w = w+'A';
    int count=0;
    string ans="Yes";

    for(int i=0; i<w.size()-1; i++){
        if(w[i]==w[i+1]) count++;
        else{
            if(count%2 == 0) {ans="No";break;}
            count=0;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

//#include "atcoder/all"
//using namespace atcoder;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> l(n);
	rep(i,n) cin >> l[i];
	sort(l.begin(), l.end());
	ll ans = 0;
	for(int i = 0; i < n-2; ++i){
		for(int j = i+1; j < n-1; ++j){
			auto idx = lower_bound(l.begin(), l.end(), l[i]+l[j]);
			ans += (--idx - l.begin()) - j;
		}
	}
	cout << ans << endl;
	return 0;
}


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

#define TRACE(x)
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

ll INF = LLONG_MAX/3;
ll safe_sum(ll a, ll b) {
    if (a == INF) return a;
    if (b == INF) return b;
    return min(a+b, INF);
}

ll safe_prod(ll a, ll b) {
    if (a == INF) return a;
    if (b == INF) return b;
    if (INF/b <= a) return INF;
    return min(INF, a * b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    int N;
    ll X;
    cin >> N >> X;

    vi x(N);
    for (int i = 0; i < N; i++)
        cin >> x[i];

    vll p(N + 1);
    for (int i = 0; i < N; i++)
        p[i+1] = p[i] + x[i];

    ll fin = LLONG_MAX;
    for (int t = 1; t <= N; t++) {
        WATCH(t);
        ll ans = X * N + X * t;
        for (int j = N - 1, sz = 1; j >= 0; j-=t, sz++) {
            int i = max(0, j - t + 1);
            ll s = p[j+1] - p[i];
            WATCH(j);
            WATCH(i);
            WATCH(s);
            if (sz == 1) ans = safe_sum(ans, 5 * s);
            else ans = safe_sum(ans, (2ll * sz + 1) * s);
        }
        WATCH(ans);
        fin = min(fin, ans);
    }

    cout << fin << endl;
    return 0;
}



Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
const long long LLINF = 1LL<<60;
const int INF = 1e9;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
#define pint pair<int,int>
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a, b, k; cin >>a >> b >> k;
    if(a<k) {
        k -= a;
        if(b<k) {
            cout << 0 << " " << 0 << endl;
        }
        else {
            cout << 0 << " " << b-k << endl;
        }
    }
    else {
        cout << a-k << " " << b << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

int main(){
    ll N;
    cin >> N;
    ll ans=1;
    for(ll i=1; i<N; i++){
        ll u, v;
        cin >> u >> v;
        if(u>v){
            ll tmp=u;
            u=v;
            v=tmp;
        }
        ans-=u*(N-v+1);
        ans+=(N-i+1)*(i+N)/2+(N-i+1)*(1-i);
    }
    cout << ans << endl;
}

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

struct UnionFind{
    vector<int> par;
    UnionFind(int n) : par(n){
       REP(i, n) par[i] = -1;
    }
    int root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    int size(int x){
        return (-par[root(x)]);
    }
    void unite(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(x > y) swap(x, y);
        if(size(x) < size(y)) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
};

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

    int n, q;
    cin >> n >> q;

    UnionFind UF(n);

    REP(i, q){
        int a, b, c;
        cin >> a >> b >> c;
        if(a){
            if(UF.same(b, c)) cout << 1 << endl;
            else cout << 0 << endl;
        }else UF.unite(b, c);
    }

    return 0;
}


Measured memory_bytes: 3256
import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	class t{
		double v = 0;
		String a = "";
	}
	
	int w[];
	int s[];
	String f[];
	
	t g(boolean[] reaming, double rw, int depth) {
		if (depth == w.length) {
			return new t();
		}
		double res = Double.MAX_VALUE;
		int dv = 0;
		String ans= "";
		for (int i = 0; i < reaming.length; i++) {
			if (reaming[i]) {
				if (rw - w[i] <= s[i]) {
					// System.out.println(i + " " +rw+" " + depth);
					reaming[i] = false;
					t gz = g(reaming, rw - w[i],  depth + 1) ;
					gz.v += rw;
					reaming[i] = true;
					if (res > gz.v) {
						res = gz.v;
						ans = gz.a;
						dv = i;
					}
				}
			}
		}
		
		ans = f[dv]+"\n"+ans;
		t ret = new t();
		ret.v = res;
		ret.a = ans;
		return ret;
	}

	void run() {
		for (;;) {
			int n = sc.nextInt();
			if (n == 0) {
				break;
			}
			f = new String[n];
			w = new int[n];
			s = new int[n];

			double rw = 0;
			for (int i = 0; i < n; i++) {
				f[i] = sc.next();
				w[i] = sc.nextInt();
				s[i] = sc.nextInt();
				rw += w[i];
			}

			boolean reaming[] = new boolean[n];
			Arrays.fill(reaming, true);
			t ans = g(reaming, rw, 0);

			System.out.print(ans.a);
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}
}

Measured memory_bytes: 12000