akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

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

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL INF = 1000000000;
const LL MOD = 1000000007;

//other
//-------------------------------------------
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define FI first
#define SE second

int main() {
  int N, ans=0;
  cin >> N;
  VI A(N), B(N), C(N-1);
  
  REP(i,N) {
    cin >> A.at(i);
  }
  
  REP(i,N) {
    cin >> B.at(i);
    ans += B.at(i);
  }
  
  REP(i,N-1) {
    cin >> C.at(i);
  }
  
  REP(i,N-1) {
    if(A.at(i)+1 == A.at(i+1)) {
      ans += C.at(A.at(i)-1);
    }
  }
  cout << ans << endl;
  return 0;
}

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

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

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

int main(){
	while(cin>>n){
		rep(i,n){
			cin>>d[i];
		}
		int p = 0;
		unsigned long long int dp[100][22]={0};//dp[i][j]
		dp[0][d[0]] = 1;
		for(int i = 1;i < n-1;i++){
			for(int j = 0;j <=20;j++){
				if(dp[i-1][j]>0){
					if(j+d[i] <=20){
						dp[i][j+d[i]] +=dp[i-1][j];
					}
					if(j-d[i]>=0)
						dp[i][j-d[i]] +=dp[i-1][j];
				}
			}
		}
		cout <<dp[n-2][d[n-1]]<<endl;
	}
	return 0;
}

Measured memory_bytes: 1176
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
    static StringBuilder builder = new StringBuilder();
 
    public static void main(String[] args) throws NumberFormatException,
            IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(
                System.in));
        int n = Integer.parseInt(reader.readLine());
        String[] a = reader.readLine().split(" ");
 
        String[] b = Arrays.copyOf(a, a.length);
        bubble(a, n);
        append(a, n);
        builder.append("Stable\n");
        selection(b, n);
        append(b, n);
        builder.append(Arrays.equals(a, b)?"Stable\n":"Not stable\n");
        System.out.print(builder);
    }
 
    public static void selection(String[] a, int n) {
 
        for (int i = 0; i < n; i++) {
            int minj = i;
            for (int j = i + 1; j < n; j++) {
                if (toInt(a, j) < toInt(a, minj)) {
                    minj = j;
                }
 
            }
            if (i != minj) {
                String tmp = a[i];
                a[i] = a[minj];
                a[minj] = tmp;
            }
        }
    }
 
    public static void bubble(String[] a, int n) {
        for (int i = 0; i < n - 1; i++) {
            for (int j = n - 1; j >= i + 1; j--) {
                if (toInt(a, j) < toInt(a, j - 1)) {
                    String temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
    }
 
    public static int toInt(String[] a, int j) {
        return a[j].charAt(1);
    }
 
    public static void append(String[] a, int n) {
        for (int k = 0; k < n; k++) {
            if (k > 0)
                builder.append(" ");
            builder.append(a[k]);
        }
        builder.append("\n");
    }
}

Measured memory_bytes: 24340
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9+7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,R,S,T,U,V,W,X,Y,Z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;

typedef pair<int, int> Pa;
typedef long long ll;

int main() {
    cin >> N;
    ll a[200000];
    ll sum = 0, num;
    rep(i, N){
        cin >> num;
        sum += num;
        a[i] = sum;
    }
    rep(i, N){
        min_value = min(min_value, abs((sum - a[i]) - a[i]));
    }
    cout << min_value;
}


Measured memory_bytes: 1792
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
using namespace std;

typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

int main(void){
    int n;
    cin >> n;
    
    vector<int> a(n), p(n), q(n);
    REP(i, n) a[i] = i+1;
    
    REP(i, n) cin >> p[i];
    REP(i, n) cin >> q[i];
    
    int x=0, y=0;
    int c = 1;
    do {
        if(a == p) x = c;
        if(a == q) y = c;
        c++;
    } while(next_permutation(ALL(a)));
    
    cout << abs(x - y) << endl;
    return 0;
}




Measured memory_bytes: 256
#B - AcCepted
S = list(input())
judge = 0
if S[0].isupper() == True:
    judge += 1
if 'C' in S[2:-1] and S.count('C') == 1:
    judge += 1
if 'C' in S:
    S.remove('C')
if 'A' in S:
    S.remove('A')
if all(S[i].islower() for i in range(len(S))) == True:
    judge += 1
if judge == 3:
    print('AC')
else:
    print('WA')

Measured memory_bytes: 9112
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

#define MOD 1000000007

typedef long long int llint;

int N;

int main() {
	cin >> N;
	vector<llint> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	llint ans = 0;
	for (int i = 0; i < 60; i++) {
		int ones = 0;
		int zeros = 0;
		for (int k = 0; k < N; k++) {
			if (A[k] & 1) { ones++; }
			else { zeros++; }
			A[k] = A[k] >> 1;
		}
		ans += ((llint)pow(2, i) % MOD * ones % MOD * zeros % MOD) % MOD;
		ans %= MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc119d
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var N = S.Length;
            var ans = 0;
            var be = S[0];
            for (int i = 1; i < N; i++)
            {
                if(be == S[i])
                {
                    if (be == '0')
                    {
                        be = '1';
                    } else
                    {
                        be = '0';
                    }
                    ans++;
                } else
                {
                    be = S[i];  
                }
            }
            Console.WriteLine(ans);
#if DEBUG
            Console.ReadKey();
#endif
        }

        private static bool IsRange(int a, int from, int to) => (from <= a && a <= to);
        private static int ReadInt() => int.Parse(Console.ReadLine());
        private static List<int> ReadIntList() => Console.ReadLine().Split().Select(int.Parse).ToList();
        private static double ReadDouble() => double.Parse(Console.ReadLine());
        private static List<double> ReadDoubleList() => Console.ReadLine().Split().Select(double.Parse).ToList();
        private static long ReadLong() => long.Parse(Console.ReadLine());
        private static List<long> ReadLongList() => Console.ReadLine().Split().Select(long.Parse).ToList();
        private static List<int> Int2Digits(int a) => a.ToString().ToCharArray().Select(_ => int.Parse(_.ToString())).ToList();
        private static int BinarySearch<Type>(IReadOnlyList<Type> s, Type target) // target 以下の最大要素のインデックスを返す
            where Type : IComparable
        {
            var lower = 0;
            var upper = s.Count - 1;
            while (upper - lower > 1)
            {
                var mid = lower + (upper - lower) / 2;
                if (s[mid].CompareTo(target) <= 0)
                {
                    lower = mid;
                }
                else
                {
                    upper = mid;
                }

            }
            return lower;
        }
    }
}


Measured memory_bytes: 13116
#!/usr/bin/ruby

require 'pp'

N, K  = gets.chomp.split(" ").map(&:to_i)
P  = gets.chomp.split(" ").map(&:to_i)

max = 0.0

0.upto(K-1){|i|
  P[i] = (P[i].to_f + 1.to_f)/2.0
  max += P[i]
}

i = K
j = 0

cur = max

while i < P.size do
  P[i] = (P[i].to_f + 1.to_f)/2.0
  cur = cur + P[i] - P[j]
  if cur > max
    max = cur
  end
  i+=1
  j+=1
end

puts max


Measured memory_bytes: 16252
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>

const int N = 10005;

int n , ans;
int num[N];

int main ( void ) {
	srand ( time ( NULL ) );
	scanf ( "%d" , &n );
	for ( int i = 1 ; i <= n ; i++ ) 
		scanf ( "%d" , &num[i] );
	num[0] = -1;
	for ( int i = 1 ; i <= n ; i++ ) {
		if ( num[i] == num[i - 1] ) {
			int to = rand () % 10000 + 1;
			while ( to == num[i - 2] || to == num[i - 1] )
				to = rand () % 10000 + 1;
			num[i] = to;
			ans++;
		}
	}
	printf ( "%d\n" , ans );
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		int min = Integer.MAX_VALUE;
		int cnt = 0;
		for (int i = 0; i < a.length; i++) {
			int t = sc.nextInt();
			a[i] = t;
			if (t <= min) {
				min = t;
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}


Measured memory_bytes: 83292
from collections import deque
n, m = map(int, input().split())
d = deque()
shirube = [0 for _ in range(n+1)]
road = [[] for _ in range(n+1)]
for i in range(m):
    r1, r2 = map(int, input().split())
    road[r1].append(r2)
    road[r2].append(r1)
for node in road[1]:
    d.append(node)
    shirube[node] = 1
while len(d) != 0:
    node = d.popleft()
    for next_node in road[node]:
        if shirube[next_node] == 0:
                d.append(next_node)
                shirube[next_node] = node 
print('Yes')
shirube_ans = shirube[2:n+1]
for s in shirube_ans:
    print(s)
    

Measured memory_bytes: 34876
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int main() {
    int a, b, c, k;
    int x, y, z;
    int flag=0;
    scanf("%d %d %d", &a, &b, &c);
    scanf("%d", &k);
    for (x=0;x<k;x++) {
        for (y=0;y<k-x;y++) {
            z=k-x-y;
            if (b*(int)pow(2,y)>a*(int)pow(2,x)&&c*(int)pow(2,z)>b*(int)pow(2,y)) flag=1;
        }
    }
    if(flag) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 2452
h,w,k = map(int, input().split())
S = [list(input()) for _ in range(h)]
ans = []
n = 1
cnt = 0
for i in range(h):
    if "#" in S[i]:
        ans = []
        for j in range(w):
            if S[i][j] == "#":
                for _ in range(j+1-len(ans)):
                    ans.append(str(n))
                n += 1
        if len(ans) < w:
            x = ans[-1]
            for _ in range(w-len(ans)):
                ans.append(x)
    if ans:
        for _ in range(i+1-cnt):
            print(" ".join(ans))
            cnt += 1

Measured memory_bytes: 9928
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {

    int a,b,c;
    cin>>a>>b>>c;
    if(a==b)cout<<c<<endl;
    if(a==c)cout<<b<<endl;
    if(c==b)cout<<a<<endl;

}


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

}

Measured memory_bytes: 3592
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IPT1_4C
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string[] inString = Console.ReadLine().Split(' ');
                if (inString[1] == "?") break;

                int numA = int.Parse(inString[0]);
                string op = inString[1];
                int numB = int.Parse(inString[2]);

                switch (op)
                {
                    case "+":
                        Console.WriteLine(numA + numB);
                        break;
                    case "-":
                        Console.WriteLine(numA - numB);
                        break;
                    case "*":
                        Console.WriteLine(numA * numB);
                        break;
                    case "/":
                        Console.WriteLine(numA / numB);
                        break;
                }
            }     
        }
    }
}

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

int main()
{
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        int d[3];
        for(int j=0; j<3; j++){
            cin>>d[j];
        }
        
        sort(d ,d+3);
        
        if(d[0]*d[0]+d[1]*d[1]==d[2]*d[2]){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    
    return 0;
}

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

/*
 * @title UnionFindTree
 */
class UnionFindTree {
	vector<int> parent,maxi,mini;
	inline int root(int n) {
		return (parent[n]<0?n:parent[n] = root(parent[n]));
	}
public:
	UnionFindTree(int N = 1) : parent(N,-1),maxi(N),mini(N){
		iota(maxi.begin(),maxi.end(),0);
		iota(mini.begin(),mini.end(),0);
	}
	inline bool connected(int n, int m) {
		return root(n) == root(m);
	}
	inline void merge(int n, int m) {
		n = root(n);
		m = root(m);
		if (n == m) return;
		if(parent[n]>parent[m]) swap(n, m);
		parent[n] += parent[m];
		parent[m] = n;
		maxi[n] = std::max(maxi[n],maxi[m]);
		mini[n] = std::min(mini[n],mini[m]);
	}
	inline int min(int n) {
		return mini[root(n)];
	}
	inline int max(int n) {
		return maxi[root(n)];
	}
	inline int size(int n){
		return (-parent[root(n)]);
	}
	inline int operator[](int n) {
		return root(n);
	}
	inline void print() {
		for(int i = 0; i < parent.size(); ++i) cout << root(i) << " ";
		cout << endl;
	}
};


int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int N,Q; cin >> N >> Q;
    UnionFindTree uf(N);
    while(Q--){
        int t,u,v; cin >> t >> u >> v;
        if(t) cout << uf.connected(u,v) << "\n";
        else uf.merge(u,v);
    }
    return 0;
}


Measured memory_bytes: 5376
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String x = br.readLine();
		String[] cut = x.split(" ");
		int a = Integer.parseInt(cut[0]);
		int b = Integer.parseInt(cut[1]);
		int c = Integer.parseInt(cut[2]);

		ArrayList<Integer> array = new ArrayList<>();
		array.add(a);
		array.add(b);
		array.add(c);

		Collections.sort(array);

		int q = array.get(0);
		int p = array.get(1);

		System.out.println(q + p);

	}
}

Measured memory_bytes: 23124
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn calc(
    seq: &Vec<Vec<i64>>,
    memo: &mut Vec<Vec<Vec<i64>>>,
    pos: usize,
    rest: usize,
    signs: usize,
) -> i64 {
    let n = memo[0].len();
    if rest == 0 {
        return 0;
    }
    if pos == n {
        return i64::min_value() / 3000;
    }
    if memo[signs][pos][rest] != i64::min_value() {
        return memo[signs][pos][rest];
    }
    let mut ret = calc(seq, memo, pos + 1, rest, signs);
    let mut sum = 0;
    for i in 0..3 {
        sum += seq[pos][i] * if ((signs >> i) & 1) == 0 { 1 } else { -1 };
    }
    sum += calc(seq, memo, pos + 1, rest - 1, signs);
    ret = std::cmp::max(ret, sum);
    memo[signs][pos][rest] = ret;
    ret
}

fn main() {
    let n = read::<usize>();
    let m = read::<usize>();
    let mut seq = vec![vec![0; 3]; n];
    for i in 0..n {
        seq[i][0] = read::<i64>();
        seq[i][1] = read::<i64>();
        seq[i][2] = read::<i64>();
    }
    let mut memo = vec![vec![vec![i64::min_value(); m + 1]; n]; 8];
    let mut ans = 0;
    for signs in 0..8 {
        ans = std::cmp::max(ans, calc(&seq, &mut memo, 0, m, signs));
    }
    println!("{}", ans);
}


Measured memory_bytes: 69884
#include <stdio.h>

int main(void) {
  int x, y;
  int d, temp;

  scanf ("%d %d", &x, &y);

  if (y > x) {
    temp = x;
    x = y;
    y = temp;
  }
  
  d = x%y;
  while (d != 0) {
    x = y;
    y = d;
    d = x%y;
  }

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

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

int main() {
  int h, w;
  cin >> h >> w;
  
  char a;
  int b;
  for(int i=0; i<=h*w; i++) {
    string s;
    cin >> s;
    if(s=="snuke") {
      a = i%w+'A';
      b = i/w+1;
      break;
    }
  }
  cout << a << b << endl;
  return 0;
}


Measured memory_bytes: 3428
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+5;
ll f[N],n,ans;
int main(){
   for(int i=1;i<N;i++) for(int j=i;j<N;j+=i) f[j]++;
   cin>>n; for(int i=1;i<=n;i++) ans+=f[i]*i; cout<<ans;
}


Measured memory_bytes: 81744
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
typedef long long ll;
using namespace std;
int main(void){
    int h,w;cin>>h>>w;
    int t[h][w];
    rep(i,h)rep(j,w){
        int x;cin>>x;
        t[i][j]=(x%2)? 1:0;
    }
    int res=0;
    queue<pair<int,int>> from,to;
    rep(j,w)rep(i,h-1){
        if(t[i][j]%2==1){
            t[i+1][j]++;
            from.push({i,j});
            to.push({i+1,j});
            res++;
        }
    }
    rep(i,w-1){
        if(t[h-1][i]%2==1){
            t[h-1][i+1]++;
            from.push({h-1,i});
            to.push({h-1,i+1});
            res++;
        }
    }
    cout<<res<<endl;
    rep(i,res){
        auto F=from.front(),T=to.front();
        from.pop();to.pop();
        cout<<F.first+1<<" "<<F.second+1<<" "<<T.first+1<<" "<<T.second+1<<endl;
    }
}


Measured memory_bytes: 5120
S = input()
A = list(map(int, list(S)))

for i in range(2**3):
  tmp = A[0]
  for j in range(3):
    if (i >> j) & 1:
      tmp += A[j+1]
    else:
      tmp -= A[j+1]
  if tmp == 7:
    ops = [S[j] + ['-','+'][(i >> j) & 1] for j in range(3)]
    print(''.join(ops) + S[3] + '=7')
    exit()

Measured memory_bytes: 3060
#include<cstdio>
#include<iostream>
using namespace std;
long long n,m;
long long gcd(long long a,long long b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	long long ans=(n*m)/gcd(n,m);
	printf("%lld\n",ans);
	return 0;
}

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


int main(){
    int n,al=0;
    cin>>n;
    vector<int> d(n);
    for(int i=0;i<n;i++){
        cin>>d[i];
        al+=d[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=d[i]*(al-d[i]);
    }
    cout<<ans/2<<endl;
}


Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_D main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif


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

    string S;  cin >> S;
    int N = S.size();

    REP(i,N-1) {
        if (S[i] == S[i+1]) {
            cout << i + 1 << ' ' << i + 2 << endl;
            return 0;
        }
    }
    REP(i,N-2) {
        if (S[i] == S[i+2]) {
            cout << i + 1 << ' ' << i + 3 << endl;
            return 0;
        }
    }

    cout << -1 << ' ' << -1 << endl;

    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

ll N, D, A;

struct xd {
	ll x;
	ll undamage;
};

int main(){
	cin >> N >> D >> A;
	vector<pii> v(N);
	
	// first = x, second = h
	for ( int i = 0; i < N; i++ ){
		cin >> v[i].first >> v[i].second;
	}
	
	sort(v.begin(),v.end());
	
	// 左から順に処理する
	ll damage = 0; // 現在位置のダメージ
	queue<xd> q; // ダメージの効果が切れる位置
	ll count = 0;
	
	for ( int l = 0; l < N; l++ ){
		ll x = v[l].first;
		ll h = v[l].second;
		
		while ( !q.empty() && q.front().x < x ){
			damage -= q.front().undamage;
			q.pop();
		}
		
		if ( h-damage > 0 ){
			ll n = (h-damage+A-1)/A;
			damage += n*A;
			q.push({x+D*2, n*A});
			count += n;
		}
	}
	
	cout << count << endl;
	
	return 0;
}



Measured memory_bytes: 3456
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
use proconio::{fastout, input};
#[fastout]
fn main() {
    input! {
        n: usize,
    }
    let mut ans = 0;
    for i in 1..n {
        ans += (n - 1) / i;
    }
    println!("{}", ans);
}


Measured memory_bytes: 2200
module app;

import core.bitop;

import std.algorithm;
import std.array;
import std.bigint;
import std.conv;
import std.stdio;
import std.string;

struct Input
{
	long h;
}

void parseInput(T)(out Input input, T file)
{
	with (file) with (input)
	{
		h = readln().strip().to!long;
	}
}

struct Output
{
}

auto main2(Input* input)
{
	return beat(input.h);
}

long beat(long n)
{
    if (n == 1)
        return 1;
    else
        return 1 + beat(n / 2) * 2;
}

unittest { writeln("begin unittest"); }

unittest // example1
{
	string example =
`2`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 3);
}

unittest // example2
{
	string example =
`4`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 7);
}

unittest // example3
{
	string example =
`1000000000000`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 1099511627775);
}

unittest { writeln("end unittest"); }

void parseExample(out Input input, string example)
{
	struct Adapter
	{
		string[] _lines;
		this(string input) { _lines = input.splitLines(); }
		string readln() { auto line = _lines[0]; _lines = _lines[1..$]; return line; }
	}
	parseInput(input, Adapter(example));
}

void main()
{
	Input input = void;
	parseInput(input, stdin);
	auto result = main2(&input);
	writeln(result);
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>

using namespace std;

int main(){
	int a, b, c, d, e, k;

	cin >> a >> b >> c >> d >> e >> k;

	if (abs(a - b) <= k&&abs(a - c) <= k&&abs(a - d) <= k&&abs(a - e) <= k&&abs(b - c) <= k&&abs(b - d) <= k&&abs(b - e) <= k&&abs(c - d) <= k&&abs(c - e) <= k&&abs(d - e) <= k)
		cout << "Yay!" << endl;
	else
		cout << ":(" << endl;
	return 0;
}

Measured memory_bytes: 256
#coding:utf-8
n = int(input())
num = []

#文字扱いにして桁数をカウントする
for i in range(1, n+1):
    num.append(str(i))

count = 0
for i in num:
    if len(i) % 2 == 1:
        count += 1

print(count)


Measured memory_bytes: 9368
import java.util.*;

class Main {

    static public int[] solve(int N, int X, int Y) {
        int[] res = new int[N-1];

        for (int i = 1; i < N; i++) {
            for (int j = i+1; j <= N; j++) {
                int d = Math.min(j-i, Math.abs(X-i) + 1 + Math.abs(Y-j));
                res[d-1]++;
            }
        }

        return res;
    }

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

        int N = sc.nextInt();
        int X = sc.nextInt();
        int Y = sc.nextInt();

        sc.close();

        for (int n : solve(N, X, Y)) {
            System.out.println(n);
        }

    }
}

Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i = 0; i * 7 <= 100; ++i){
		for(int j = 0; j * 4 <= 100; ++j){
			if(i * 7 + j * 4 == n){
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	} 
	cout<<"No"<<endl;
	return 0;
}

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

using namespace std;

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

	vector<int> h(n);
	for (int i = 0; i < n; i++)
	{
		cin >> h.at(i);
	}
	sort(h.begin(), h.end());

	int ans = INT_MAX;
	for (int i = 0; i <= n - k; i++)
	{
		ans = min(ans, h.at(i + k - 1) - h.at(i));
	}

	cout << ans << endl;
}

Measured memory_bytes: 640
import math
N,D = [int(i) for i in input().split()]
X = [input().split() for i in range(N)]
cnt = 0
for i in range(N-1):
    for j in range(i+1,N):
        d = 0
        for k in range(D):
            d += (int(X[i][k])-int(X[j][k]))**2
        d = math.sqrt(d)
        if d%1==0:
            cnt+=1
print("{}".format(cnt))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
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<int> a(n);
    rep(i, n) cin >> a[i];
    map<int, int> ans;
    rep(i, n) ans[a[i]]++;
    int count = 0;
    for(auto p : ans) {
        if(p.second % 2 == 1) count++;
    }
    cout << count << endl;
}


Measured memory_bytes: 8196
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
int main(void){
    int num,map[4],i,o;
    char mapc[4]="mcxi",line1[9],line2[9];
    scanf("%d",&num);
    for(o=0;o<num;o++){
        memset(map,0,sizeof(map));
        scanf("%s %s",line1,line2);
        i=0;
        while(line1[i]){
            if('0'<=line1[i] && line1[i] <= '9'){
                if(line1[i+1] == 'm')
                    map[0]+=line1[i]-48;
                if(line1[i+1] == 'c')
                    map[1]+=line1[i]-48;
                if(line1[i+1] == 'x')
                    map[2]+=line1[i]-48;
                if(line1[i+1] == 'i')
                    map[3]+=line1[i]-48;
                i++;
            }
            else{
                if(line1[i] == 'm')
                    map[0]+=1;
                if(line1[i] == 'c')
                    map[1]+=1;
                if(line1[i] == 'x')
                    map[2]+=1;
                if(line1[i] == 'i')
                    map[3]+=1;
            }
            i++;
        }i=0;
        while(line2[i]){
            if('0'<=line2[i] && line2[i] <= '9'){
                if(line2[i+1] == 'm')
                    map[0]+=line2[i]-48;
                if(line2[i+1] == 'c')
                    map[1]+=line2[i]-48;
                if(line2[i+1] == 'x')
                    map[2]+=line2[i]-48;
                if(line2[i+1] == 'i')
                    map[3]+=line2[i]-48;
                i++;
            }
            else{
                if(line2[i] == 'm')
                    map[0]+=1;
                if(line2[i] == 'c')
                    map[1]+=1;
                if(line2[i] == 'x')
                    map[2]+=1;
                if(line2[i] == 'i')
                    map[3]+=1;
            }
            i++;
        }
        for(i=3;i>=0;i--){
            if(map[i] >= 10){
                map[i-1]++;
                map[i]%=10;
            }
        }
        for(i=0;i<4;i++){
            if(map[i] == 1)
                printf("%c",mapc[i]);
            else if(map[i] != 0)
                printf("%d%c",map[i],mapc[i]);
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 604
n=int(input())
l=list(map(int,input().split()))
for i in range(n):
  sum1=0
  sum2=0
  for j in range(0,i+1):
    sum1+=l[j]
  for k in range(i+1,n):
    sum2+=l[k]
  if i==0:
    ans=abs(sum1-sum2)
  else:
    if abs(sum1-sum2)<ans:
      ans=abs(sum1-sum2)
print(ans)

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

using namespace std;

int main(){
	int n,m,k; cin >> n >> m >> k;
	bool flag = false;
	for(int i = 0; i <=n; i++){
		for(int j = 0; j <=m; j++){
			if(i*m+j*n-2*(i*j) == k){
				flag = true;
				break;
			}
		}
		if(flag)break;
	}
	if(flag) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}



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

int main() {
  string S, T;
  cin >> S >> T;
  int ans = 0;
  for (int i = 0; i < S.size(); ++i) {
    if (S[i] != T[i]) {
      ++ans;
    }
  }
  cout << ans << endl;
}


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

//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = (LL)INF * INF;

const int MAX = 5007;

LL dp[MAX][MAX];
int p[MAX];

void upd(LL& x, LL val)
{
	x = min(x, val);
}

int main()
{
	//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, a, b;
	cin >> n >> a >> b;
	FOR(i, 1, n + 1)
		cin >> p[i];
	FOR(i, 0, n + 1)
		FOR(j, 0, n + 1)
			dp[i][j] = LINF;
	dp[0][0] = 0;
	FOR(i, 0, n)
		FOR(j, 0, i + 1)
		{
			if(p[i + 1] > p[j])
				upd(dp[i + 1][i + 1], dp[i][j]);
			upd(dp[i + 1][j], dp[i][j] + (p[i + 1] > p[j] ? a : b));
		}
	LL ans = LINF;
	FOR(j, 0, n + 1)
		upd(ans, dp[n][j]);
	cout << ans;
	return 0;
}

Measured memory_bytes: 195840
#include <bits/stdc++.h>
    #include <algorithm>
    #include <cctype>
    #include <iostream>
    #define rep(i,n) for(int i = 0; i < (n); i++)
     
    using namespace std;  
    
    
    
    int main() {
     
     string w;
     cin >> w;
     int count = 0;
     while(true){
    	string t;
     	cin >> t;
     	if(t == "END_OF_TEXT"){
     		break;
     	} else{
     		std::transform(t.begin(),t.end(),t.begin(),::tolower);
     		if(t.find(w) != -1)	{
     			if(t.size() == w.size()){
     				count++;
     			} else{
     				int a = t.find(w);
     				if((a>0 && isalpha(t[a-1])) || a < t.size() -1 && isalpha(t[a+w.size()]))	continue;
     				else count++;
     			}
     		}
     	}
     
     }
     cout << count << '\n';
     return 0;
    }
    


Measured memory_bytes: 3224
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> h(n);
    rep(i,n){
        cin>>h[i];
    }
    sort(h.rbegin(),h.rend());
    ll ans = 0;
    for(int i=k;i<n;i++){
        ans+=h[i];
    }
    cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 1920
H, W = map(int, input().split())
a = ['.'*(W+2)]
for i in range(H):
    a.append('.'+input()+'.')
a.append('.'*(W+2))
x, y = 1, 1
d = [0, 1], [1, 0]

#右と下だけで行けるところまで行く
while True:
    #現在地を探索済みにする
    a[x] = a[x][:y] + '*' + a[x][y+1:]
    
    if [x, y] == [H, W]:
        break
    
    #右か下に進む
    for d_i in d:
        if a[x+d_i[0]][y+d_i[1]]=='#':
            x, y = x+d_i[0], y+d_i[1]
            break
    #行き止まりなら終了
    else:
        break
    
    
#探索結果を確認
end = 0
for r_i in a:
    for j in r_i:
        if j == '#':
            print('Impossible')
            end = 1
            break
    if end == 1:
        break
else:
    print('Possible')

Measured memory_bytes: 3064
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);;

	int INF=1<<28;
	double EPS=1e-9;

	void run(){
		String line=sc.nextLine();
		String s="";
		boolean first=true;
		for(char c : line.toCharArray()){
			if(c==' '||c=='.'||c==','){
				if(s.length()>=3&&s.length()<=6){
					print((first?"":" ")+s);
					first=false;
				}
				s="";
			}else{
				s+=c;
			}
		}
		if(s.length()>=3&&s.length()<=6){
			print((first?"":" ")+s);
		}
		println("");
	}

	void run_(){
		// String regex="(^| |[,]|\\.)+(\\p{Alpha}{3,6}?)($| |[,]|\\.)+";
		// String regex="(\\G| |[,]|\\.)+(\\p{Alpha}{3,6}?)($| |[,]|\\.)+";
		String regex="(\\G|^| |[,]|\\.)+(\\p{Alpha}{3,6}?)($| |[,]|\\.)+";
		Pattern pattern=Pattern.compile(regex);
		Matcher matcher=pattern.matcher(sc.nextLine());
		if(matcher.find()){
			for(;;){
				print(matcher.group(2));
				// debug(matcher.group());
				if(matcher.find()){
					print(" ");
				}else{
					break;
				}
			}
		}
		// println("");
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

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

Measured memory_bytes: 12000
#include <iostream>
#include <vector>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, s, n) for(int i = s; i < n; i++)
using namespace std;

int main(){
  int n;
  cin >> n;
  int m = sqrt(n);
  int num = n;
  cout << n << ':';
  rep2(i, 2, m+1){
    while(num%i==0){
      num /= i;
      cout << ' ' << i;
    }
  }
  if (num != 1) cout << ' ' << num;
  cout << endl;
  
  return 0;
}


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

using namespace std ;

const int MAX = 1e5 + 10 ;

long long freq[MAX] ;
int n ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	long long ans = 0ll ;
	for(int i = 0 ; i < n ; ++i)
	{
		int x ;
		cin>>x ;
		ans += x ;
		freq[x]++ ;
	}
	int q ;
	cin>>q ;
	while(q--)
	{
		int a , b ;
		cin>>a>>b ;
		ans -= freq[a] * a ;
		ans += freq[a] * b ;
		freq[b] += freq[a] ;
		freq[a] = 0 ;
		cout<<ans<<"\n" ;
	}
	return 0 ;
}		

Measured memory_bytes: 4432
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b;
  string s;
  cin >> n >> a >> b >> s;
  int abroad=0,pass=0;
  for(int i=0;i<n;i++){
    if(s[i]=='c'){
      cout << "No" << endl;
      continue;
    }
    if(s[i]=='a'){
      if(pass < (a+b)){
        cout << "Yes" << endl;
        pass++;
      }else{
        cout << "No" << endl; 
      }
    }
    if(s[i]=='b'){
      abroad++;
      if(pass < (a+b) && abroad <= b){
        cout << "Yes" << endl;
        pass++;
      }else{
        cout << "No" << endl;
      }
    }
  }
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 45;
const int mod = 1000000007;

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int n, m;
  ll x;
  cin >> n >> m >> x;
  vector<ll> c(n);
  vector<vector<ll>> book(n, vector<ll>(m));
  rep(i, n) {
    cin >> c[i];
    rep(j, m) cin >> book[i][j];
  }
  ll ans = INF64;
  for(int bit = 1; bit < 1<<n; ++bit) {
    vector<ll> r(m, 0);
    ll charge = 0;
    rep(i, n) if(bit & 1<<i) {
      charge += c[i];
      rep(j, m) r[j] += book[i][j];
    }
    bool ok = true;
    rep(j, m) if(r[j] < x) ok = false;
    if(ok) chmin(ans, charge);
  }
  cout << ((ans != INF64) ? ans : -1) << endl;
}

Measured memory_bytes: 3664
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H;
long long int ans;


int main() {
	ios::sync_with_stdio(false);
	string s, t;
	cin >> s >> t;
	if (s.size() > t.size()) {
		cout << "GREATER\n";
		return 0;
	}
	if (s.size() < t.size()) {
		cout << "LESS\n";
		return 0;
	}
	for (int i = 0; i < s.size(); i++) {
		if (s[i] > t[i]) {
			cout << "GREATER\n";
			return 0;
		}
		if (s[i] < t[i]) {
			cout << "LESS\n";
			return 0;
		}
	}
	cout << "EQUAL\n";
	return 0;
}

Measured memory_bytes: 256
def main():
    s = open(0).readlines()

    x, y, a, b, c = map(int, s[0].split())
    f = lambda x: list(map(int, x.split()))

    p, q, r = map(f, s[1:])

    p = sorted(p, reverse=True)
    q = sorted(q, reverse=True)
    r = sorted(r, reverse=True)

    p = p[:x]
    q = q[:y]

    i = max(r)
    j = sum(x > i for x in p)
    k = sum(x > i for x in q)

    pd = p[j:]
    qd = q[k:]

    m = (x - j) + (y - k)

    rem = sorted(pd + qd + r, reverse=True)
    ans = sum(p[:j] + q[:k]) + sum(rem[:m])
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 25536
#include<bits/stdc++.h>
using namespace std;
#define max1 10000005
#define siz 100000
#define mod 998244353
#define inf 1e18+5
#define ll long long int
#define debug(x) cout<<#x<<" "<<x<<endl
#define jam(x) cout<<"Case #"<<x<<": "
typedef pair<ll,ll> pr;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  /*#ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif*/
  ll n,w;
  cin>>n>>w;
  vector<ll> a(n+1),wt(n+1);
  for(ll i=1;i<=n;i++)
  {
    cin>>wt[i]>>a[i];
  }
  vector<vector<ll> > dp(2,vector<ll>(100005,inf));
  dp[0][0]=0;
  for(ll i=1;i<=n;i++)
  {
    ll x=i%2;
    for(ll j=0;j<=100000;j++)
    {
      if(j>=a[i])
      {
        dp[x][j]=min(dp[x^1][j],dp[x^1][j-a[i]]+wt[i]);
      }
      else
      {
        dp[x][j]=dp[x^1][j];
      }
    }
  }
  ll ans=0;
  for(ll i=100000;i>=1;i--)
  {
    if(dp[n%2][i]<=w)
    {
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<0<<endl;
}

Measured memory_bytes: 2560
#include<cstdio>
#include<queue>
using namespace std;

typedef const int& cint;
const int Inf = 0x3f3f3f3f;
const int MAXN = 500010;

int p[MAXN];
int nxt[2][MAXN], deg[MAXN], ans[MAXN];

inline int Min(int a, int b){return a < b ? a : b;}

inline void chkmin(int& a, int b){if (b < a) a = b;}

inline int Max(int a, int b){return a > b ? a : b;}

inline void chkmax(int& a, int b){if (b > a) a = b;}

class segmentTree{
	int size, mn[MAXN << 2];
	
	void pushup(cint idx){
		mn[idx] = Min(mn[idx << 1], mn[idx << 1 | 1]);
	}
	
	void build(int l, int r, int idx){
		if (l == r){
			mn[idx] = Inf;
			return;
		}
		int mid = l + r >> 1;
		build(l, mid, idx << 1), build(mid + 1, r, idx << 1 | 1);
		pushup(idx);
	}
	
	void change(cint pos, cint nval, int l, int r, int idx){
		if (l == r){
			mn[idx] = nval;
			return;
		}
		int mid = l + r >> 1;
		if (pos <= mid)
			change(pos, nval, l, mid, idx << 1);
		else
			change(pos, nval, mid + 1, r, idx << 1 | 1);
		pushup(idx);
	}
	
	int query(cint li, cint ri, int l, int r, int idx){
		if (li <= l && r <= ri)
			return mn[idx];
		int mid = l + r >> 1, res = Inf;
		if (li <= mid)
			chkmin(res, query(li, ri, l, mid, idx << 1));
		if (mid < ri)
			chkmin(res, query(li, ri, mid + 1, r, idx << 1 | 1));
		return res;
	}
	
	public:
		void build(cint size_){
			size = size_, build(1, size, 1);
		}
		
		void change(cint pos, cint nval){
			change(pos, nval, 1, size, 1);
		}
		
		int query(cint li, cint ri){
			if (ri < li) return Inf;
			return query(li, ri, 1, size, 1);
		}
}seg;

priority_queue<int, vector<int>, greater<int> > q;

int main(){
	int N, K;
	scanf("%d %d", &N, &K);
	for (int i = 1, tmp; i <= N; ++i)
		scanf("%d", &tmp), p[tmp] = i;
	seg.build(N);
	seg.change(p[N], N); 
	for (int i = N - 1, tmp; i >= 1; --i){
		tmp = seg.query(Max(1, p[i] - K + 1), p[i] - 1);
		if (tmp != Inf)
			nxt[0][p[i]] = p[tmp], ++deg[p[tmp]];
		tmp = seg.query(p[i] + 1, Min(N, p[i] + K - 1));
		if (tmp != Inf)
			nxt[1][p[i]] = p[tmp], ++deg[p[tmp]];
		seg.change(p[i], i); 
	}
	for (int i = 1; i <= N; ++i)
		if (!deg[i])
			q.push(i);
	int u, cnt = 0;
	while (!q.empty()){
		u = q.top(), q.pop();
		ans[u] = ++cnt;
		if (nxt[0][u]){
			--deg[nxt[0][u]];
			if (!deg[nxt[0][u]])
				q.push(nxt[0][u]);
		}
		if (nxt[1][u]){
			--deg[nxt[1][u]];
			if (!deg[nxt[1][u]])
				q.push(nxt[1][u]);
		}
	}
	for (int i = 1; i <= N; ++i)
		printf("%d\n", ans[i]);
	return 0;
}


Measured memory_bytes: 21876
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " ";
#define INF 10000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    vi ans(4, 0);
    vec(string) na = {"AC", "WA", "TLE", "RE"};
    lli n;
    cin >> n;
    rep(i,n){
        string s;
        cin >> s;
        if(s[0]=='A'){
            ans[0]++;
        }
        else if(s[0]=='W'){
            ans[1]++;
        }
        else if(s[0]=='T'){
            ans[2]++;
        }
        else{
            ans[3]++;
        }
    }
    rep(i,4){
        out(na[i] + " x "<<ans[i]);
    }
}

Measured memory_bytes: 3640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC091B
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());

            string[] s = new string[N];
            for (int i=0; i < N; i++)
            {
                s[i] = Console.ReadLine();
            }

            var M = int.Parse(Console.ReadLine());

            string[] t = new string[M];
            for (int i = 0; i < M; i++)
            {
                t[i] = Console.ReadLine();
            }

            int max = 0;
            for(int i = 0; i < s.Count(); i++)
            {
                int count = 0;
                for(int j = 0; j < s.Count(); j++)
                {
                    if (s[j] == s[i]) count++;
                }
                for (int j = 0; j < t.Count(); j++)
                {
                    if (t[j] == s[i]) count--;
                }
                max = Math.Max(max, count);
            }

            Console.WriteLine(max);
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13268
import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))
    val Array(n, p) = in.readLine().split("\\s+").map(_.toInt)
    val as = in.readLine().split("\\s+").map(_.toInt)

    val oddCount = as.count(_ % 2 != 0)

    out.println(
      if (oddCount == 0) {
        if (p == 0) {
          Math.pow(2, n).toLong
        } else {
          0
        }
      } else {
        Math.pow(2, n - 1).toLong
      }
    )
    out.flush()
  }
}


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

using namespace std;

int main()
{
	int n,d,s=0,x=0;
	cin >> n;
  	for (int i=0; i < n; i++)
    {
    	cin >> d;
      	s=s+d;
      	x=x+d*d;
    }
  	s=s*s;
  	s=s-x;
  	cout << s/2;
}

Measured memory_bytes: 256
using System;
using System.Linq;

public class AtCoder_150_A
{
    public static void Main()
    {
        //var exStdIn = new System.IO.StreamReader( "input.txt" );
        //System.Console.SetIn( exStdIn );

        int[] nums = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
        int count = nums[0];
        int threshold = nums[1];
        Console.WriteLine(count * 500 >= threshold ? "Yes" : "No");
    }
}


Measured memory_bytes: 13268