akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n, L[120], R[120], LX[120], RX[120], LD[120], RD[120];
int INF = 999999;
int main() {
	while (true) {
		cin >> n; if (n == 0) { break; }
		for (int i = 0; i < n; i++)cin >> L[i];
		for (int i = 0; i < n; i++)cin >> R[i];
		for (int i = 0; i < n; i++) {
			if (L[i] == 0) { LX[i] = i; }
			if (L[i] == 1) {
				for (int j = i; j < n; j++) {
					if (L[j] != 1) { break; }
					LX[i] = j;
				}
			}
			if (L[i] == 2) {
				for (int j = i; j >= 0; j--) {
					LX[i] = j;
					if (L[j] != 2) { break; }
				}
			}
			if (R[i] == 0) { RX[i] = i; }
			if (R[i] == 1) {
				for (int j = i; j < n; j++) {
					if (R[j] != 1) { break; }
					RX[i] = j;
				}
			}
			if (R[i] == 2) {
				for (int j = i; j >= 0; j--) {
					RX[i] = j;
					if (R[j] != 2) { break; }
				}
			}
		}
		for (int i = 0; i < n; i++) { LD[i] = INF; RD[i] = INF; }
		queue<pair<int, int>>Q; Q.push(make_pair(0, LX[0])); Q.push(make_pair(1, RX[0])); LD[LX[0]] = 0; RD[RX[0]] = 0;
		while (!Q.empty()) {
			pair<int, int>pa = Q.front(); Q.pop();
			int a1 = pa.first, a2 = pa.second;
			if (a1 == 0) {
				if (RD[RX[a2]] == INF) { RD[RX[a2]] = LD[a2] + 1; Q.push(make_pair(1, RX[a2])); }
				if (RD[RX[a2 + 1]] == INF && a2 + 1 < n) { RD[RX[a2 + 1]] = LD[a2] + 1; Q.push(make_pair(1, RX[a2 + 1])); }
				if (RD[RX[a2 + 2]] == INF && a2 + 2 < n) { RD[RX[a2 + 2]] = LD[a2] + 1; Q.push(make_pair(1, RX[a2 + 2])); }
			}
			if (a1 == 1) {
				if (LD[LX[a2]] == INF) { LD[LX[a2]] = RD[a2] + 1; Q.push(make_pair(0, LX[a2])); }
				if (LD[LX[a2 + 1]] == INF && a2 + 1 < n) { LD[LX[a2 + 1]] = RD[a2] + 1; Q.push(make_pair(0, LX[a2 + 1])); }
				if (LD[LX[a2 + 2]] == INF && a2 + 2 < n) { LD[LX[a2 + 2]] = RD[a2] + 1; Q.push(make_pair(0, LX[a2 + 2])); }
			}
		}
		int V = min(LD[n - 1], RD[n - 1]);
		if (V == INF) { cout << "NA" << endl; }
		else { cout << V << endl; }
	}
}

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

#define int long long
int lb=-2e18,ub=2e18;

signed main() {
    int n,k,a[200000];
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);

    while(ub-lb>1){
        int mid=(ub+lb)/2,cnt=0;
        for(int i=0;i<n;i++){
            if(a[i]<0)
            	cnt+=min(n-(lower_bound(a,a+n,(long double)mid/a[i])-a),n-i);
            else if(a[i]>0)
            	cnt+=upper_bound(a+i,a+n,(long double)mid/a[i])-(a+i);
            else if(mid>=0)
            	cnt+=n-i;
			if(a[i]*a[i]<=mid) cnt--;
        }
        (cnt>=k?ub:lb)=mid;
    }
    cout<<ub<<endl;
	return 0;
}

Measured memory_bytes: 1792
import java.util.HashMap;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int d = sc.nextInt();
    int[] array_c = new int[27];
    int[][] array_s = new int[d + 1][27];
    int[] schedule = new int[d + 1];
    HashMap<Integer, Integer> last = new HashMap<>();
    for(int i = 1; i <= 26; i++){
      array_c[i] = sc.nextInt();
      last.put(i, 0);
    }
    for(int i = 1; i <=d; i++){
      for(int j = 1; j <= 26; j++){
        array_s[i][j] = sc.nextInt();
      }
    }
    for(int i = 1; i <= d; i++){
      schedule[i] = sc.nextInt();
    }

    int m = 0;
    for(int i = 1; i <= d; i++){
      last.put(schedule[i], i);
      m += array_s[i][schedule[i]];
      for(int j = 1; j <= 26; j++){
        m -= (i - last.get(j)) * array_c[j];
      }
      System.out.println(m);
    }
  }
}

Measured memory_bytes: 46244
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K, answer = 0;
  cin >> N >> K;
  vector<int> h(N);
  for (int i = 0; i < N; i++) {
    cin >> h.at(i);
  }
  for (int i = 0; i < N; i++) {
    if (h.at(i) >= K) answer++;
  }
  cout << answer << endl;
}

Measured memory_bytes: 640
import java.util.*;

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

        int N = sc.nextInt();
        long ans = 0;
        
        for(int i=1; i<N; i++){
            ans += i;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        String S = scan.next();
        char[] data = S.toCharArray();
        int[] sum = new int[N+1];
        Arrays.fill(sum, 0);
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            if (data[i] == '#') {
                sum[i+1] += sum[i] + 1;
                continue;
            }
            sum[i+1] += sum[i];
        }
        for (int i = 0; i <= N; i++) {
            answer = Math.min(sub(N, sum, i), answer);
        }
        System.out.println(answer);
    }
    public static int sub(int N, int[] sum, int from) {
        int blackcount_before_from = sum[from];
        int whitecount_before_from = from - sum[from];
        int whitecount_after_from = N - sum[N] - whitecount_before_from;
        return blackcount_before_from + whitecount_after_from;
    }
}


Measured memory_bytes: 29528
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = (int)1e5 + 10;

int n, m;
vector<int> v[N];

int dis[N][3];
bool vis[N];

void dijkstra(int source, int destination){

   for (int i = 0; i <= n; ++i){
      for (int j = 0; j < 3; ++j)
      {
         dis[i][j] = inf;
      }
   }

//if one is the source vertex
   dis[source][0] = 0;
   multiset<pair<int, int> > s;
   s.insert({0, source});

   while(!s.empty()){
      pair<int, int> p = *(s.begin());
      s.erase(s.begin());

      int distance = p.F, x = p.S;

      if (x == destination and distance % 3 == 0){
         cout<<distance/3;
         exit(0);
      }

      for(auto i: v[x]){
         if(dis[x][distance%3] + 1 < dis[i][(distance+1)%3]){
            dis[i][(distance+1)%3] = dis[x][distance%3] + 1;
            s.insert({dis[i][(distance+1)%3], i});
         }
      }
   }

   cout<<-1;
   exit(0);
}

int32_t main(){_

   cin>>n>>m;  

   for (int i = 0; i < m; ++i)
   {
      int x, y;
      cin>>x>>y;
      v[x].pb(y);
   }

   int source, destination;
   cin>>source>>destination;

   dijkstra(source, destination);   

   return 0;
}

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

int n, a[200005];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	if(a[1] != 0) {
		puts("-1");
		return 0;
	}
	long long ans = 0;
	for(int i=1;i<=n;i++) {
		if(a[i] > a[i-1] + 1) {
			puts("-1");
			return 0;
		}
		if(a[i] < a[i-1] + 1) {
			ans += a[i-1];
		}
	}
	ans += a[n];
	printf("%lld\n",ans);
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <vector>
#include <string>
using namespace std;
 
 
int main() {
  int N, diff;
  //vector<string> blue_str(100), red_str(100);
  vector<int> point(100), point_a(50), point_b(50);
  
  cin >> N;
  for (int i = 0; i < N; i++) { 
    cin >> point.at(i); 
  }
  
  vector<int>::iterator max;
  int index;
  for (int i = 0; i < N; i++) {
    max = max_element(point.begin(), point.end());
    index = distance(point.begin(), max);
    if (i%2 == 0) { 
      point_a.push_back(point.at(index));
    }
    else { 
      point_b.push_back(point.at(index));
    }
    point.erase(point.begin() + index);
  }
  int sum_a = accumulate(point_a.begin(), point_a.end(), 0);
  int sum_b = accumulate(point_b.begin(), point_b.end(), 0);
  
  diff = sum_a - sum_b;
  cout << diff << endl;
}

Measured memory_bytes: 256
class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod


def main():
    mod = 10**9+7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    c = Combi(N, mod)
    res = 0
    for i, v in enumerate(A):
        res += c.com(i, K-1)*v
        res -= c.com(N-1-i, K-1)*v
        res %= mod
    print(res)
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 20880
package main

import (
	"strconv"
	"bufio"
	"os"
	"strings"
	"fmt"
)

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_C>
 */

func init() {

}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	for {
		scanner.Scan()
		stringInput := scanner.Text()
		stringSplited := strings.Split(stringInput," ")
		x,_ := strconv.Atoi(stringSplited[0])
		y,_ := strconv.Atoi(stringSplited[1])
		if x== 0 && y == 0{
			break
		}
		if x > y{
			x,y = y,x
		}
		fmt.Println(x,y)
	}
}

// ????????????1?????????
func StrStdin() (stringReturned string) {
	scanner := bufio.NewScanner(os.Stdin)

	scanner.Scan()
	stringInput := scanner.Text()

	stringReturned = strings.TrimSpace(stringInput)
	return
}

// ??´??°???1?????????
func IntStdin() (int, error) {
	stringInput := StrStdin()
	return strconv.Atoi(strings.TrimSpace(stringInput))
}

// ?????????????????????????????????????????????Split()
func SplitWithoutEmpty(stringTargeted string, delim string) (stringReturned []string) {
	stringSplited := strings.Split(stringTargeted, delim)

	for _, str := range stringSplited {
		if str != "" {
			stringReturned = append(stringReturned, str)
		}
	}

	return
}

// ??????????????§??????????????????????????????????????????
func SplitStrStdin(delim string) (stringReturned []string) {
	// ???????????§1?????????
	stringInput := StrStdin()

	// ????????§??????
	// stringSplited := strings.Split(stringInput, delim)
	stringReturned = SplitWithoutEmpty(stringInput, delim)

	return
}

// ??????????????§??????????????´??°????????????????????????
func SplitIntStdin(delim string) (intSlices []int, err error) {
	// ??????????????????????????????
	stringSplited := SplitStrStdin(" ")

	// ??´??°?????????????????????
	for i := range stringSplited {
		var iparam int
		iparam, err = strconv.Atoi(stringSplited[i])
		if err != nil {
			return
		}
		intSlices = append(intSlices, iparam)
	}
	return
}

Measured memory_bytes: 1172
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
const int MAXN = 100 ;

int g[3][MAXN+10];
int sum[3][MAXN+10];
int n;

int main()
{
    cin >> n ;

    for(int i = 1; i <= n; i++)
    {
        cin >> g[1][i] ;
        sum[1][i] = g[1][i] + sum[1][i-1];
    }

    for(int i = 1; i <= n; i++)
        cin >> g[2][i] ;
    for(int i = n; i >= 1; i--)
        sum[2][i] = g[2][i] + sum[2][i+1];

    int ans = 0;

    for(int i = 1; i <= n; i++)
        ans = max(ans, sum[1][i]+sum[2][i]);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b, c;
    cin>>a>>b>>c;
    if (a==b && b==c){
        cout<<"No\n";
        return 0;
    }
    if (a==b || b==c || a==c){
        cout<<"Yes\n";
        return 0;
    }
    cout<<"No\n";
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
const int inf = 1e9;

int main() {
  int N, K, S; cin >> N >> K >> S;
  int cnt = 0;
  for(int i = 0; i < N; i++) {
    if(cnt < K) {
      cout << S;
      cnt++;
    } else {
      cout << (S==inf ? S-1 : S+1);
    }
    if(i==N-1) cout << endl;
    else cout << " ";
  }
  return 0;
}


Measured memory_bytes: 1280
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int a[]=new int[N/2];
		int b[]=new int[N/2];
		int d[]=new int[100001]; 
		int f[]=new int[100001]; 
		int l=N/2;
		for(int i=0;i<N/2;i++) {
			a[i]=in.nextInt();
			b[i]=in.nextInt();
		}
		
		for (int i = 0; i < l; i++) {
			d[a[i]]++;				// 頻度を数える：a[i]の値に該当する頻度値を1増やす
		}
		int max=1;
		int maxse=1;
		for (int i = 1; i < 100001; i++) {
			if (d[i] > d[max]) {
				maxse=max;
				max = i;			// 最大頻度を求める
			}
		}
		for (int i = 1; i < 100001; i++) {
			if (d[i] > d[maxse]&&!(i==max)) {
				maxse = i;			// 最大頻度を求める
			}
		}
		
		for (int i = 0; i < l; i++) {
			f[b[i]]++;				// 頻度を数える：a[i]の値に該当する頻度値を1増やす
		}
		
		int max2=1;
		int maxse2=1;
		for (int i = 1; i < 100001; i++) {
			if (f[i] > f[max2]) {
				max2 = i;			// 最大頻度を求める
			}
		}
		for (int i = 1; i < 100001; i++) {
			if (f[i] > f[maxse2]&&!(i==max2)) {
				maxse2 = i;			// 最大頻度を求める
			}
		}
		
	    if(l-d[max]==0&&l-f[max2]==0&&b[0]==a[0]) {
	    	System.out.println(l);
	    }else if(max==max2){
	    	System.out.println(Math.min(2*l-d[max]-f[maxse2],2*l-d[maxse]-f[max2]));
	    }else {
	    	System.out.println(l-d[max]+(l-f[max2]));	    	
	    }

	}
}

Measured memory_bytes: 59992
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	ans := 0
	a_cnt := 0
	b_prev := false
	for i := 0; i < len(s); i++ {
		if s[i] == 'A' {
			if b_prev {
				a_cnt = 0
			}
			a_cnt++
			b_prev = false
		}
		if s[i] == 'B' {
			if b_prev {
				a_cnt = 0
			}
			b_prev = true
		}
		if s[i] == 'C' {
			if b_prev {
				ans += a_cnt
			} else {
				a_cnt = 0
			}
			b_prev = false
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1920
#include<stdio.h>
#define M 1000000
int main(){

  int i,n,q,l,r,mid,C=0,S[M],T[M];

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&T[i]);
  }
  
  for(i=0;i<q;i++){
    l=0;
    r=n;
  while(l<r){
    mid=(l+r)/2;
    if(T[i]==S[mid]){
      C++;
      break;
    }
    if(T[i]>S[mid]){
      l=mid+1;
    }
    else if(T[i]<S[mid]){
      r=mid;
    }
    
  }

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



Measured memory_bytes: 2296
#include <cstdio>
using namespace std;
#define MAX 10000
#define NIL -1

struct Node {
	int parent;
	int left;
	int right;
};

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].left, d + 1);
	setDepth(T[u].right, d + 1);
}

int setHeight(int u)
{
	int h1 = 0, h2 = 0;
	
	if (T[u].left != NIL) {
		h1 = setHeight(T[u].left) + 1;
	}
	if (T[u].right != NIL) {
		h2 = setHeight(T[u].right) + 1;
	}

	return H[u] = (h1 > h2) ? h1 : h2;
}

int getSibling(int u)
{
	if (T[u].parent == NIL) {
		return NIL;
	}
	if (T[T[u].parent].left != u&&T[T[u].parent].left != NIL) {
		return T[T[u].parent].left;
	}
	if (T[T[u].parent].right != u&&T[T[u].parent].right != NIL) {
		return T[T[u].parent].right;
	}

	return NIL;
}

void print(int u)
{
	printf("node %d: ", u);
	printf("parent = %d, ", T[u].parent);
	printf("sibling = %d, ", getSibling(u));

	int deg = 0;

	if (T[u].left != NIL) {
		deg++;
	}
	if (T[u].right != NIL) {
		deg++;
	}

	printf("degree = %d, ", deg);
	printf("depth = %d, ", D[u]);
	printf("height = %d, ", H[u]);

	if (T[u].parent == NIL) {
		printf("root\n");
	}
	else if (T[u].left == NIL&&T[u].right == NIL) {
		printf("leaf\n");
	}
	else {
		printf("internal node\n");
	}
}

int main()
{
	int v, l, r, root = 0;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		T[i].parent = NIL;
	}

	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &v, &l, &r);
		T[v].left = l;
		T[v].right = r;

		if (l != NIL) {
			T[l].parent = v;
		}
		if (r != NIL) {
			T[r].parent = v;
		}
	}

	for (int i = 0; i < n; i++) {
		if (T[i].parent == NIL) {
			root = i;
		}
	}

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

	for (int i = 0; i < n; i++) {
		print(i);
	}

	return 0;
}

Measured memory_bytes: 2768
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    string S;
    cin >> S;
    int n = S.length();
    string S1 = S.substr(0, n/2);
    string S2 = S.substr(n/2+1, n/2);

    auto f = [](string s){
        int n = s.length();
        REP(i, n/2){
            if(s[i]!=s[n-1-i]){
                return false;
            }
        }
        return true;
    };

    if(!f(S)){
        pr("No");
        return 0;
    }
    if(!f(S1) || !f(S2)){
        pr("No");
        return 0;
    }

    pr("Yes");
}

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

using namespace std;

int to_num(char c)
{
    if (isdigit(c)) {
        return c - '0';
    } else if (isupper(c)) {
        return c - 'A' + 10;
    } else {
        return c - 'a' + 36;
    }
}

int change(int p, string m)
{
    int res = 0;
    reverse(m.begin(), m.end());
    for (int i = 0; i < (int)m.size(); i++) {
        res += to_num(m[i]) * pow(p, i);
    }
    return res;
}

int main()
{
    int N, p, x = 0;
    string m;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> p >> m;
        x ^= change(p, m);
    }
    cout << (x != 0 ? "win" : "lose") << endl;
    return 0;
}

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

int main() {
    int N;
    string ans = "", S, T;
    cin >> N >> S >> T;
    for(int i = 0; i < N; i++) {
        ans += S.substr(i,1) + T.substr(i,1);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <cstdlib>
using namespace std;
 
#define DEBUG(x) cerr << #x << " = " << x << endl
 
bool isX(const string& s) {
    return s == "x";
}
 
int toInt(const string& from) {
    if(isX(from)) abort();
    stringstream ss;
    int to; ss << from; ss >> to; return to;
}
 
int main() {
    for(int N; cin >> N, N; ) {
        vector<string> vec(N);
        for(int i = 0; i < N; i++) {
            cin >> vec[i];
        }
 
        bool f = false;
        for(int i = 1; i < N; i++) {
            if(isX(vec[i - 1]) && isX(vec[i])) f = true;
            if(i % 2 == 0) {
                if(!isX(vec[i - 1]) && !isX(vec[i]) && !(toInt(vec[i - 1]) > toInt(vec[i]))) f = true;
            }
            else {
                if(!isX(vec[i - 1]) && !isX(vec[i]) && !(toInt(vec[i - 1]) < toInt(vec[i]))) f = true;
            }
        }
 
        if(f) {
            cout << "none" << endl;
            continue;
        }
 
        int upper = (int)1e9 + 2;
        int lower = -((int)1e9 + 2);
        for(int i = 0; i < N; i++) {
            if(isX(vec[i])) {
                if(i % 2 == 0) {
                    if(i > 0) {
                        upper = min(upper, toInt(vec[i - 1]) - 1);
                    }
                    if(i < N - 1) {
                        upper = min(upper, toInt(vec[i + 1]) - 1);
                    }
                } else {
                    if(i > 0) {
                        lower = max(lower, toInt(vec[i - 1]) + 1);
                    }
                    if(i < N - 1) {
                        lower = max(lower, toInt(vec[i + 1]) + 1);
                    }
                }
            }
        }
        if(lower == upper) {
            cout << lower << endl;
        }
        else if(lower > upper) {
            cout << "none" << endl;
        }
        else {
            cout << "ambiguous" << endl;
        }
    }
}

Measured memory_bytes: 1296
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int main(){
int A,B,C,D,train,bus,sum;
cin>>A>>B>>C>>D;
train=min(A,B);
bus=min(C,D);
sum=train+bus;
cout<<sum<<endl;



























}


Measured memory_bytes: 256
def main():
    s=input()
    a,b,c,d=int(s[0]),int(s[1]),int(s[2]),int(s[3])
    now0=a
    for op1 in [-1,1]:
        now1=now0+op1*b
        for op2 in [-1,1]:
            now2=now1+op2*c
            for op3 in [-1,1]:
                now3=now2+op3*d
                if now3==7:
                    return [a,b,c,d],[op1,op2,op3]
d,p=main()
ans=str(d[0])
for i in range(3):
    if p[i]==-1:ans+='-'
    elif p[i]==1:ans+='+'
    ans+=str(d[i+1])
ans+='=7'
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
	ll n,ans=0,temp,cnt=1;cin>>n;
  	vector<ll> a(n+1);for(int i=0;i<n;i++) cin>>a[i];
  	a[n]=1000000001;
  	sort(a.begin(),a.end());
  	temp=a[0];
  	for(int i=1;i<n+1;i++){
      //	cout<<temp<<" "<<a[i]<<" "<<cnt<<endl;
      	if(a[i]==temp){
        	cnt++;
        }else{
        	if(cnt%2!=0){
             	ans++;
            }
          	cnt=1;
            temp=a[i];
        } 	
    }
  	cout<<ans<<endl;
}

Measured memory_bytes: 1024
#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 <math.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<long long> h(n);
    for(int i=0; i<n; i++){
        cin >> h.at(i);
    }
    if(n==1){
        cout << "Yes" <<endl;
    }
    else{
        for(int i=0; i<n-1; i++){
            if(h.at(i)>h.at(i+1)){
                h.at(i+1)++;
            }
            if(h.at(i)>h.at(i+1)){
                cout << "No" << endl;
                break;
            }
            else if(i==n-2){
                cout << "Yes" <<endl;
            }
        }
    }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 using namespace std;
 int N, A[3][3], b[10];
 bool appear[3][3];
 int main() {
 for(int i = 0; i < 3; i++) {
 for(int j = 0; j < 3; j++) cin >> A[i][j];
 }
 cin >> N;
 for(int i = 0; i < N; i++) cin >> b[i];
 for(int i = 0; i < N; i++) {
 for(int j = 0; j < N; j++) {
 appear[i][j] = false;
 for(int k = 0; k < N; k++) {
 if(A[i][j] == b[k]) appear[i][j] = true;
 }
 }
 }
 string ANS = "No";
 for(int i = 0; i < 3; i++) {
 if(appear[i][0] and appear[i][1] and appear[i][2]) ANS = "Yes";
 }
 for(int i = 0; i < 3; i++) {
 if(appear[0][i] and appear[1][i] and appear[2][i]) ANS = "Yes";
 }
 if(appear[0][0] and appear[1][1] and appear[2][2]) ANS = "Yes";
 if(appear[0][2] and appear[1][1] and appear[2][0]) ANS = "Yes";
 cout << ANS << endl;
 return 0;
 }


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

typedef long long ll;
typedef vector<long long> VLL;
typedef vector<pair<int,int>> VP;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
/*--------------------------------------------*/

int main(){
  string s;
  cin >> s;
  
  s.insert(s.begin(),'a');
  s.insert(s.end(),'a');
  
  int N = s.size();
  
  vector<pair<char,int> > t;
  
  rep(i,N){
    if(s[i] != 'x'){
      t.PB(MP(s[i],i));
    }
  }
  
  int M = t.size();
  
  int cost = 0;
  
  if(M % 2 == 0){
    rep(i,M/2){
      if(t[i].first != t[M-i-1].first){
        cout << -1 << endl;
        return 0;
      }
    }
    
    for(int i = M/2;i > 1;i--){
      int left = t[i-1].second - t[i-2].second-1;
      int right = t[M-i+1].second - t[M-i].second-1;
      cost += abs(left-right);
    }
      
  }else{
    rep(i,(M-1)/2){
      if(t[i].first != t[M-i-1].first){
        cout << -1 << endl;
        return 0;
      }
    }
      
    for(int i = (M-1)/2;i > 0;i--){
      int left = t[i].second - t[i-1].second-1;
      int right = t[M-i].second - t[M-i-1].second-1;
      cost += abs(left-right);
    }
    
  }

  cout << cost << endl;
  
}

Measured memory_bytes: 1528
#include<iostream>
#include<cstdio>
using namespace std;
int main() {
	int n,m,q,a[2005];
	scanf("%d%d%d",&n,&m,&q);
	for (register int i=1;i<=n;++i) {
		scanf("%d",a+i);
	}
	int l=0,r=2000000000;
	while (l<r) {
		int mid=(l+r)>>1;
		bool ok=0;
		for (register int i=1;i<=n;++i) {
			int p=a[i],k=0,tmp=0,cnt=0;
			for (register int j=1;j<=n+1;++j) {
				if (a[j]<p||j==n+1) {
					tmp+=j-k-1<m?0:min(j-k-1-m+1,j-k-1-cnt);
					k=j;
					cnt=0;
				}
				else if (a[j]>p+mid) {
					++cnt;
				}
			}
			if (tmp>=q) {
				ok=1;
				break;
			}
		}
		ok?r=mid:l=mid+1;
	}
	printf("%d",l);
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#include<deque>
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define per(i,n) for(ll i=n-1;i>=0; --i)
#define all(x) (x).begin(),(x).end()
#define _GLIBCXX_DEBUG
using namespace std;
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; }
const long long INF = 1LL << 60;
typedef long long ll;
const ll MOD = 1000000007;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	ll a, b;
	cin >> a >> b;
	cout << max(0LL,a - b*2) << endl;
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000






int main() {
	long double a[N];
	long double b[N];
	vector<pair<long double,int> >c;
	int n, k;
	long double x, y, z,xx,yy;
	long double s, ans;
	bool v = true;
	ans = 0;
	scanf("%d", &n);
	f(i, n) {
		scanf("%Lf %Lf", &a[i], &b[i]);
		if ((abs(a[i])<= 0.01) && (abs(b[i]) <= 0.01)) {
			n--;
			i--;
		}
		else {
			x = (a[i] * a[i]) + (b[i] * b[i]);
			x = sqrt(x);
			x = a[i] / x;
			y = acos(x);
			if (b[i] > -0.5) {
				c.push_back(make_pair(y,i));
			}
			else {
				y = ((2*(3.1415926535897933))-y);
				c.push_back(make_pair(y, i));
			}
		}

	}
	if (n == 0) {
		printf("0.000000000000\n");
		return 0;
	}
	sort(c.begin(), c.end());
	f(i, n) {
		x = 0;
		y = 0;
		f(j, n) {
				k = (i + j) % n;
				x += a[c[k].second];
				y += b[c[k].second];
				z = (x*x) + (y*y);
				z = sqrt(z);
				ans = max(ans, z);
		}
	}
	printf("%.13Lf\n", ans);
	return 0;
}

Measured memory_bytes: 2304
#include<iostream>
#include<cmath>
#include<utility>
#include<algorithm>
using namespace std;

int main(){
    int n;
    float y;
    pair<float, int> pi[100];
    while(1){
        cin >> n;
        if(!n) break;
        cin >> y;
        for(int i = 0;i < n;i++){
            int b, t;
            float r;
            cin >> b >> r >> t;
            float a;
            if(t == 1){
                a = 1 + y * r / 100;
            }else{
                a = pow(1 + r / 100, y);
            }
            pi[i].first = a; pi[i].second = b;
        }
        sort(pi, pi + n);
        cout << pi[n - 1].second << endl;
    }
    
    return 0;
}

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

int w,h,count;
char room[20][20];

void rec(int y, int x){
  if(y<0||x<0||y>=h||x>=w){
      return;
    }
    if(room[y][x] == '#'){
      return;
    }
    count++;
    room[y][x] = '#';
    rec(y-1,x);
    rec(y,x+1);
    rec(y+1,x);
    rec(y,x-1);
    }
  
  int main(){
    
    int i,j,x,y;
    while(1){
      count=0;
      cin >> w >> h;
      if( w==0 && h==0){
	break;
      }
      for(j = 0;j < h;j++){
	for(i = 0;i < w;i++){ 
	  cin >> room[j][i] ;
	  if(room[j][i] =='@'){
	    x = i;
	    y = j;
	  }
	}
      }

      rec(y,x);
      cout << count << endl;
    }
  }

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int a;
  cin >> a;
  while(a--){
    const Int n = 9;
    vector<Int> as(n),bs(n);
    for(Int i=0;i<n;i++) cin >> as[i];
    for(Int i=0;i<n;i++) cin >> bs[i];
    sort(as.begin(),as.end());
    Int num=0,cnt=0;
    do{
      Int x=0,y=0;
      for(Int i =0;i<n;i++){
        if(as[i]<bs[i]) x+=as[i]+bs[i];
        if(as[i]>bs[i]) y+=as[i]+bs[i];
      }
      if(x<y) num++;
      cnt++;
    }while(next_permutation(as.begin(),as.end()));
    double A=(double)num/cnt;
    double B=1.0-A;
    cout << fixed<<setprecision(5);
    cout << A << " " << B << endl;


  }
  return 0;
}



Measured memory_bytes: 3300
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int k;
    cin>>k;
    cin>>s;
    if(s.length()<=k)
    cout<<s;
    else
    {
        vector<char>v;
        for(auto itr : s)
        v.push_back(itr);
        for(int i=0;i<k;i++)
        cout<<v[i];
        cout<<"...";
    }
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>//ソートなどに必要
using namespace std;

long findSumOfDigits(long n) 
{//引数をnとして、nの各桁の数の和を求める
  long sum = 0;
  while (n > 0) 
  { // n が 0 になるまで
    sum += n % 10;//一の位から順に数をたす
    n /= 10;//10なら次は１、9なら終了になる
  }
  return sum;
}

int main() 
{
    long n;
    cin >> n;
    long a = findSumOfDigits(n);

    if(n % a == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 1 << 30
#define EPS 1e-10

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int n, w;

int main(){
  while(scanf("%d%d", &n, &w) && n+w){
    int m = 0, v;
    int tail = 0;
    vi h(100/w+1, 0);
    rep(i, n){
      scanf("%d", &v);
      h[v/w]++;
      if(h[v/w] == 1) tail = max(tail, v/w);
      m = max(m, h[v/w]);
    }

    int num = tail;
    double res = 0;
    rep(i, tail) res += (double)h[i]/(double)m*(double)num--/(double)tail;
    printf("%lf\n", res+0.01);
  }
  return 0;
}

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

int main()
{
    int x;
    set<int> s;
    for(int i = 1; i <= 3; i++) {cin >> x; s.insert(x);}
    if(s.size() == 2) cout << "Yes\n";
    else cout << "No\n";

}


Measured memory_bytes: 256
n = int(input())
p = [int(i) for i in input().split()]
ans = 0
for i in range(n-2):
  if p[i] < p[i+1] and p[i+1] < p[i+2]:
    ans += 1
  elif p[i] > p[i+1] and p[i+1] > p[i+2]:
    ans += 1
print(ans) 

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

int main(){
	int a, b, c, first, middle, last;
	cin >> a >> b >> c;

	if(a < b){
		first = a;
		middle = b;}
	else{
		first = b;
		middle = a;}
	
	if(middle < c){
		last = c;}
	else{
		if(first < c){
			last = middle;
			middle = c;} // first, lastは変動なし
		else{
			last = middle;
			middle = first;
			first = c;
			}
	}
	cout << first << " " << middle << " " << last << endl;
	return 0;
}


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

int main()
{
    string s;
    cin >> s;

    char even, odd;
    if (s[0] == '0')
    {
        even = '0'; odd = '1';
    }
    else
    {
        even = '1'; odd = '0';
    }

    int res = 0;
    for (int i=0; i<s.length(); i++)
    {
        if (i%2 == 0 && s[i] != even) res++;
        if (i%2 == 1 && s[i] != odd) res++;
    }

    cout << res << endl;
}

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

int gcd(int m, int n) {
    if (n == 0) {
    	return m;  
    }
    return gcd(n, m % n);
}

int main() {
	int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];  
    }
    
    vector<int> L(n + 1);
    L[0] = 0;
    for (int i = 1; i <= n; ++i) {
        L[i] = gcd(L[i - 1], A[i - 1]);
    }
    vector<int> R(n + 1);
    R[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        R[i] = gcd(R[i + 1], A[i]);  
    }
  
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, gcd(L[i], R[i + 1]));  
    }
      
    cout << ans << endl;  
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
#include <set>
#include <cstdio>
#include <climits>
#include <cmath>
#include <array>
#include <functional>
#include <sstream>
#include <list>
#include <set>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const double eps=1e-9;
const int inf=1e9;
typedef pair<int,int> P;
struct Point
{
  double x,y;
  Point(){x=0;y=0;}
  Point(double d_x,double d_y){x=d_x,y=d_y;}
  double operator*(Point obj){return obj.x*x+obj.y*y;}
  double operator%(Point obj){return obj.y*x-obj.x*y;}
  Point operator*(double b){Point tmp;tmp.x=x*b;tmp.y=y*b;return tmp;}
  Point operator/(double b){Point tmp;tmp.x=x/b;tmp.y=y/b;return tmp;}
  Point operator+(Point obj){Point tmp;tmp.x=x+obj.x;tmp.y=y+obj.y;return tmp;}
  Point operator-(){Point tmp;tmp.x=-x;tmp.y=-y;return tmp;}
  Point operator-(Point obj){Point tmp;tmp.x=x-obj.x;tmp.y=y-obj.y;return tmp;}
  Point operator-=(Point obj){x-=obj.x;y-=obj.y;return *this;}
  Point operator+=(Point obj){x+=obj.x;y+=obj.y;return *this;}
  Point operator/=(double b){x=x/b;y=y/b;return *this;}
  Point operator*=(double b){x=x*b;y=y*b;return *this;}
  double size(){return hypot(x,y);}
  Point unit(){return Point(x/size(),y/size());}
  Point normal(){return Point(y,-x);}
  double atan(){return atan2(y,x);}
};

bool operator<(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
bool operator>(Point a,Point b){return b<a;}
bool operator<=(Point a,Point b){return !(b<a);}
bool operator>=(Point a,Point b){return !(a<b);}
bool operator==(Point a,Point b){return (a-b).size()<eps;}
bool operator!=(Point a,Point b){return !(a==b);}

bool equal(double a,double b){return abs(a-b)<eps;}
double cross(Point a,Point b){return a%b;}
double dot(Point a,Point b){return a*b;}

int ccw(Point a,Point b,Point c)
{
  b=b-a;
  c=c-a;
  if(b%c>0) return +1;
  else if(b%c<0)return -1;
  else if(b*c<0) return +2;
  else if(b.size()<c.size()) return -2;
  else return 0;
}


int times[100005];
int n;

void calc(string str,int v)
{
  stringstream ss(str);
  int h,m,s;
  char c;
  ss >> h >> c >> m >> c >> s;
  times[h*60*60+m*60+s]+=v;
}


int main(int argc,char const* argv[])
{
  while(1)
    {
      memset(times,0,sizeof(times));
      cin >> n;
      if(!n)break;
      for(int i=0;i<n;i++)
	{
	  string start,goal;
	  cin >> start >> goal;
	  calc(start,1);
	  calc(goal,-1);
	}
      for(int i=1;i<100000;i++)
	{
	  times[i]+=times[i-1];
	}
      int ans=0;
      for(int i=0;i<100000;i++)
	{
	  ans=max(ans,times[i]); 
	}
      cout << ans << endl;
    }
  return 0;
}



Measured memory_bytes: 3408
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  int t;

  cin>>t;

  for(int i=0;i<t;++i){
    int n,k;
    vector<int> x;
    vector<int> distance;
    int temp;
    int total=0;
    
    cin>>n>>k;

      for(int j=0;j<n;++j){
	cin>>temp;
	x.push_back(temp);
      }

      if(n<=k)
	cout<<0<<endl;
      else{
	total=temp-x[0];
      
	for(int j=0;j<n-1;++j)
	  distance.push_back(x[j+1]-x[j]);
	
	sort(distance.begin(),distance.end(),greater<int>());
	
	for(int j=0;j<k-1;++j)
	  total-=distance[j];
	
	cout<<total<<endl;
      }
  }
  return 0;
}

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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e2 + 1;
const int MAX_W = 1e4 + 1;

int dp[MAX_N][MAX_W];

int N, W;

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

  cin >> N >> W;
  vector< int > v(N), w(N);
  REP(i, N)
    cin >> v[i] >> w[i];

  REP(i, W + 1) {
    dp[0][i] = 0;
  }
  
  REP(i, N) {
    REP(j, W + 1) {
      if (j < w[i]) {
	dp[i + 1][j] = dp[i][j];
      } else {
	dp[i + 1][j] = max(dp[i][j],
			   dp[i][j - w[i]] + v[i]);
      }
    }
  }

  int ans = 0;
  REP(i, W + 1) {
    ans = max(ans, dp[N][i]);
  }

  cout << ans << endl;

  return 0;
}




Measured memory_bytes: 7092
package main

import (
	"fmt"
)

const MOD = 1000000007

func ModAdd(a, b int64) int64 {
	return (a + b) % MOD
}

func ModMul(a, b int64) int64 {
	return a * b % MOD
}

func ModSub(a, b int64) int64 {
	r := (a%MOD - b%MOD) % MOD
	if r < 0 {
		r += MOD
	}
	return r
}

func ModDiv(a, b int64) int64 {
	return a % MOD * ModInv(b) % MOD
}

func ModPow(a, n int64) int64 {
	var r int64 = 1
	for n > 0 {
		if n&1 == 1 {
			r = r * a % MOD
		}
		a = a * a % MOD
		n >>= 1
	}
	return r
}

func ModInv(a int64) int64 {
	var b, u, v int64 = MOD, 1, 0
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= MOD
	if u < 0 {
		u += MOD
	}
	return u
}

type Q struct {
	idx, value int
	a, b       int
	index      int
}

type QS []*Q

func (p QS) Len() int           { return len(p) }
func (p QS) Less(i, j int) bool { return p[i].value > p[j].value }
func (pq QS) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *QS) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Q)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *QS) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func FactoredPrimeNumber(num int) map[int]int {
	m := map[int]int{}
	return factor(m, num, 2)
}

func factor(result map[int]int, num, pnum int) map[int]int {
	if pnum*pnum > num {
		if num != 1 {
			result[num] += 1
		}
		return result
	}

	if num%pnum == 0 {
		num /= pnum
		result[pnum]++
	} else {
		pnum++
	}
	return factor(result, num, pnum)
}

func GCD(a, b int) int {
	if b == 0 {
		return a
	}
	return GCD(b, a%b)
}

func LCM(a, b int) int {
	return a * b / GCD(a, b)
}

var R = [][]int{}

func main() {
	var A, B, N int
	fmt.Scanf("%d %d %d\n", &A, &B, &N)
	x := B - 1
	if x > N {
		x = N
	}
	fmt.Println((A * x) / B)
}

func Reverse(runes []rune) []rune {
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return runes
}


Measured memory_bytes: 1816
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
nizi = [0] * (10**5+1)
for i in range(len(A)):
    # print(A[i], A)
    nizi[A[i]] += 1
sumall = sum(A)
for q in range(Q):
    # print(nizi)
    B, C = map(int, input().split())
    sumall += (C-B) * nizi[B]
    nizi[C] += nizi[B]
    nizi[B] = 0
    print(sumall)

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

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

  vector<vector<int>> jobs(m + 1);
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    if (a > m) continue;
    jobs[m - a].push_back(b);
  }

  priority_queue<int> q;
  ll ans = 0;
  for (int i = m - 1; i >= 0; i--) {
    for (int b : jobs[i]) {
      q.push(b);
    }
    if (!q.empty()) {
      ans += q.top();
      q.pop();
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s[2];
	cin >> s[0] >> s[1];
	
	for (int i = 0; i < 3; i++) {
		if (s[0][i] != s[1][2 - i]) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
}

Measured memory_bytes: 256
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	ans = 0
	maxsum = A[0]
	for i in range(1, N):
		ans += max(0, maxsum - A[i])
		maxsum = max(maxsum, A[i])

	print(ans)

if __name__ == '__main__':
	main()

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

int main(){
	int m, n;
	while(cin >> m >> n, m){
		int ans = 0;
		for(int i = m; i <= n; i++){
			int num = i;
			while(1){
				if(num == 1){
					ans++;
					break;
				}
				else if(num % 2 != 0 && num % 3 != 0 && num % 5 != 0) break;
				if(num % 2 == 0) num /= 2;
				else if(num % 3 == 0) num /= 3;
				else if(num % 5 == 0) num /= 5;
			}
		}
		cout << ans << endl;
	}
}

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

#define ll long long
#define MOD 1000000007

ll bigmod(ll n , ll p)
{
    if(p==0) return 1;
    else if(p%2==0){
        ll ret=bigmod(n,p/2);
        return ((ret%MOD)*(ret%MOD))%MOD;
    }
    else
        return ((n%MOD)*(bigmod(n,p-1)%MOD))%MOD;
}



int main()
{
    ll n,a,b,d,l=1,h=1,cnt=0;
    cin>>n>>a>>b;
    d=bigmod(2,n);

    for(int i=n,j=a;i<=(a-1),j>=1;i--,j--){
        //cout<<i<<" "<<j<<endl;
        l=((l%MOD)*(((i%MOD)*bigmod(j,MOD-2)%MOD)))%MOD;
    }

    //cout<<l<<endl;

    for(int i=n,j=b;i<=(b-1),j>=1;i--,j--){
        h=((h%MOD)*(((i%MOD)*bigmod(j,MOD-2)%MOD)))%MOD;
    }
    
    //cout<<h<<endl;
    
    d=(d-(l+h)%MOD)%MOD-1;
    if(d<0) d+=MOD;
    cout<<d<<"\n";

}


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

int main(){

    string N;
    cin >> N;

    int sum = 0;
    for(int i = 0; i < N.length(); i++){
        sum += N[i] - '0';
    }

    if(stoi(N) % sum) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <stack>

using namespace std;

typedef long long ll;
#define mem(a) (memset(a,0,sizeof(a)))
#define rep(i, n) for(int (i)=0;(i)<(n);(i)++)
#define MAX(a, b) ((a)>(b)?(a):(b))
#define MIN(a, b) ((a)<(b)?(a):(b))

const int maxn = static_cast<const int>(1e3 + 5);
const int mod = static_cast<const int>(1e9);

int t[maxn], a[maxn];
ll T[maxn], A[maxn];

int main() {
    int n;
    ll ak, tk, k;
    scanf("%d", &n);
    rep(i, n)scanf("%d%d", &t[i], &a[i]);
    T[0] = t[0];
    A[0] = a[0];
    for (int i = 1; i < n; i++) {
        if (t[i] >= T[i - 1] && a[i] >= A[i - 1]) {
            T[i] = t[i];
            A[i] = a[i];
        } else {
            if (A[i - 1] % a[i] == 0)ak = A[i - 1] / a[i];
            else ak = A[i - 1] / a[i] + 1;
            if (T[i - 1] % t[i] == 0)tk = T[i - 1] / t[i];
            else tk = T[i - 1] / t[i] + 1;
            k = MAX(ak, tk);
            A[i] = a[i] * k;
            T[i] = t[i] * k;

        }
    }
    printf("%lld\n", T[n - 1] + A[n - 1]);

    return 0;
}

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

using namespace std;

#define N 100000

int x[N + 1];

int main(){
	int ans, n, i;

	scanf("%d%d", &n, x + 0);

	for (i = 1; i <= n; i++){
		scanf("%d", x + i);
	}

	sort(x + 0, x + 1 + n);

	ans = 0;

	for (i = 1; i <= n; i++){
		ans = __gcd(ans, x[i] - x[i - 1]);
	}

	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <ostream>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstring>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using ll = long long;

template <typename T, typename U>
std::ostream& operator << (std::ostream& out, std::pair<T, U> p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}

template <typename T>
std::ostream& operator << (std::ostream& out, std::vector<T> v) {
  out << "[";
  for (int i = 0; i < v.size(); ++i) {
    out << v[i] << (i == (v.size() - 1) ? "" : ", ");
  }
  out << "]";
  return out;
}



int main() {

  int n, k;

  cin >> n >> k;

  int ans = 0;

  for (int i = 1; i <= n; i+=2) {
    ans++;
  }

  if (ans >= k) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <vector>
#include<string>
#include<algorithm>
 int n,cnt=1;
bool val(int a[],int b[])
{
    for(int i=0;i<n;i++)
    {
        if(a[i]!=b[i])
            return false;
    }
    return true;
}
using namespace std;
int main()
{
 cin>>n;
 int arr[n],arr1[n],arr2[n];
 for(int i=0;i<n;i++)
 {
    cin>>arr1[i];
     arr[i]=arr1[i];
 }
 int ans,ans2;
    for(int i=0;i<n;i++)
    cin>>arr2[i];
    sort(arr,arr+n);
    do
    {
      if(val(arr1,arr))
        ans=cnt;
      if(val(arr2,arr))
        ans2=cnt;
    cnt++;
    }while(next_permutation(arr,arr+n));
    cout<<abs(ans-ans2);
}


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

int main() {
    int N, M, T;
    cin >> N >> M >> T;

    vector<int> a(N);
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }

    int ans = a[0] - M;
    for(int i = 1; i < N; i++) {
        if(a[i] - a[i-1] > 2 * M) {
            ans += a[i] - a[i-1] - 2 * M;
        }
    }
    if(T - a[N-1] > M) {
        ans += T - a[N-1] - M;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3100