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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    UnionFind(int N) : par(N),siz(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++){
             par[i] = i;
             siz[i] = 1;
        }
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        // merge technique（小を大にくっつける）
        if (siz[rx] < siz[ry]) swap(rx, ry);
        siz[rx] += siz[ry];
        par[ry] = rx;
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    ll size(ll x){
        return siz[root(x)];
    }
};

signed main(){
    gearup;
    ll n,m;cin>>n>>m;
    vb c(n),d(n);
    rep(i,m){
        int a,b;cin>>a>>b;
        a--;b--;
        if(a==0)c[b]=true;
        if(b==n-1)d[a]=true;
    }
    bool is_res = false;
    rep1(i,n-1){
        if(c[i] && d[i])is_res = true;
    }
    cout << (is_res?"POSSIBLE":"IMPOSSIBLE") << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){

	int N,M;
	int i;
	int masu[2000] = { 0 };
	int dice[2000] = { 0 };
	int count;
	int loc;


	while (1){

		count = 0;
		loc = 1;

		scanf("%d %d", &N, &M);

		if (N == 0 && M == 0)break;

		for (i = 0; i < N; i++)	{
			scanf("%d", &masu[i]);

		}

		for (i = 0; i < M; i++){
			scanf("%d", &dice[i]);

		}

		while (loc < N){
			

			loc += masu[loc-1];
			
			
			if (loc >= N)break;

			loc += dice[count];
			
			count++;

		}

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

	}

	return 0;
}

Measured memory_bytes: 616
#include <iostream>
using namespace std;
int main() {
  string s;
  cin >> s;
  if(s == "Rainy"){
    cout << "Sunny" << endl;
  }
  else if(s == "Sunny"){
    cout << "Cloudy" << endl;
  }
  else if (s == "Cloudy"){
    cout << "Rainy" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
ll strtoint(string str);
int main(){
	fast;
	ll n; cin>>n;
	string s; cin>>s;
	for(auto i=0;i<s.size();++i){
		if(char(s[i]+n)<='Z')cout<<char(s[i]+n);
		else{
			ll cnt=0;
			while(s[i]<='Z'){
				s[i]=char(s[i]+1);
				++cnt;
			}
			s[i]='A';
			cout<<char(s[i]+n-cnt);
		}
	}
	return 0;
}
ll strtoint(string str){
	ll x=0;
	stringstream ss;
	ss<<str;
	ss>>x;
	return x;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int task[3];
    for(int i = 0; i < 3; i++){
        cin >> task[i];
    }
    bool flag = false;
    int cache;
    while(1){
        flag = false;
        for(int i = 0; i < 2; i++){
            if(task[i] > task[i+1]){
                cache = task[i];
                task[i] = task[i+1];
                task[i+1] = cache;
                flag = true;
            }
        }
        if(!flag){
            break;
        }
    }
    cout << (abs(task[1] - task[0]) + abs(task[2] - task[1])) << endl;
}

Measured memory_bytes: 256
x1, y1, x2, y2 = gets.chomp.split.map(&:to_i)

x = x2 - x1
y = y2 - y1

x3 = x2 - y
y3 = y2 + x
x4 = x3 - x
y4 = y3 - y

puts "#{x3} #{y3} #{x4} #{y4}"



Measured memory_bytes: 1788
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define VV(T,h,w)    move(vector<vector<T>>(h,move(vector<T>(w))))
#define VVI(T,h,w,i) move(vector<vector<T>>(h,move(vector<T>(w,i))))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
	ll a = in(), b = in();
	cout << (a * b % 2 == 0 ? "Even" : "Odd") << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
int main(){
	ios::sync_with_stdio(false);
	int a,b,c=1;
	cin>>a>>b;
	for(;c<=3;c++){
		if(a*b*c%2!=0){
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N,count;
  cin >> N;
  for (int i=0; i < 5; i += 2){
    
  	if (N >= pow(10, i+1)) count +=  pow(10, i+1) - pow(10, i);
  	else{
    	if (N >= pow(10, i)) count += N - pow(10, i) + 1;
    }
  }
 
  
  cout << count << endl;
}

Measured memory_bytes: 256
/*#include <bits/stdc++.h>
using namespace std;
string ans,s[3055][3055],s1,s2;
int dp[3055][3055],n,m,ma;
int main()
{

    cin>>s1>>s2;
    if (s1.size()>s2.size()) swap(s1,s2);
    n=s1.size();
    m=s2.size();
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
        {
            dp[i+1][j+1]=dp[i][j+1];
            s[i+1][j+1]=s[i][j+1];
            if (s1[i]==s2[j])
            {
                    dp[i+1][j+1]++;
                    s[i+1][j+1]=s[i+1][j+1]+s1[i];
            }
            if (dp[i+1][j+1]<=dp[i+1][j])
            {
                s[i+1][j+1]=s[i+1][j];
                dp[i+1][j+1]=dp[i+1][j];
            }
            //cout<<s[i+1][j+1]<<dp[i+1][j+1]<<" ";
        }

    }
    for (int i=0;i<=m;i++)
    {
        if (dp[n][i]>ma)
        {
            ma=dp[n][i];
            ans=s[n][i];
        }
    }
    cout<<ans;
}*/
#include<bits/stdc++.h>
using namespace std;
int n;
bool vis[3009][3009];
int p[3009],dp[300900],k,a[1000],ans;
int main()
{

    cin>>n>>k;
    for (int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for (int i=0;i<=k;i++)
    {
        for (int j=0;j<n;j++)
        {
            dp[i+a[j]]=max(dp[i+a[j]],1-dp[i]);
        }
    }
    if (dp[k]==1) cout<<"First";
    else cout<<"Second";
}


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

using namespace std;

int rowid[100], colid[100];

int main(){
    int row, col, i, j, flag=0;
    scanf("%d %d ", &row, &col);
    char mat[row][col+1];
    for(i=0; i<row; i++){
        for(j=0; j<col; j++) scanf("%c", &mat[i][j]);
        cin.ignore();
    }
    /*for(i=0; i<row; i++){
        for(j=0; j<col; j++) printf("%c", mat[i][j]);
        printf("\n");
        //getchar();
    }*/
    for(i=0; i<row; i++){
        flag=0;
        for(j=0; j<col; j++){
            if(mat[i][j]=='#'){
                flag=1;
                break;
            }
        }
        if(!flag&1) rowid[i]=1;
    }
    for(i=0; i<col; i++){
        flag=0;
        for(j=0; j<row; j++){
            if(mat[j][i]=='#'){
                flag=1;
                break;
            }
        }
        if(!flag&1) colid[i]=1;
    }
    for(i=0; i<row; i++){
        if(!rowid[i]&1){
            for(j=0; j<col; j++){
                if(!colid[j]&1) printf("%c", mat[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}


Measured memory_bytes: 256
from itertools import product

N, M = map(int, input().split())
sss = []
for _ in range(M):
    k, *ss = map(int, input().split())
    sss.append(ss)
ps = list(map(int, input().split()))

ans = 0
for ptn in product(range(2), repeat=N):
    numL = 0
    for ss, p in zip(sss, ps):
        numON = 0
        for s in ss:
            numON += ptn[s-1]
        if numON%2 == p:
            numL += 1
    if numL == M:
        ans += 1

print(ans)


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

#define f first
#define s second
#define pb push_back
#define all(c) c.begin(),c.end()

#define gi(x) scanf("%d", &x)
#define pi(x) printf("%d", x)
#define gl(x) scanf("%lld", &x)
#define pl(x) printf("%lld", x)
#define sp printf(" ")
#define nl printf("\n")

typedef long long int lld;
typedef long double ldb;

main(){
    int n, m;
    cin >> n >> m;
    string  str[n];
    for(int i = 0; i < n; ++i) cin >> str[i];
    auto f = [n, m](int i, int j){
        if(i < n and i >= 0 and j >= 0 and j < m) return 1;
        return 0;
    };
    auto toChar = [](int i){
        return (char)(i + '0');
    };
    int cnt = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cnt = 0;
            if(str[i][j] == '.'){
                if(f(i-1, j-1)) cnt += (str[i-1][j-1] == '#');
                if(f(i-1, j))   cnt += (str[i-1][j] == '#');
                if(f(i-1, j+1)) cnt += (str[i-1][j+1] == '#');
                if(f(i, j-1))   cnt += (str[i][j-1] == '#');
                if(f(i, j+1))   cnt += (str[i][j+1] == '#');
                if(f(i+1, j-1)) cnt += (str[i+1][j-1] == '#');
                if(f(i+1, j))   cnt += (str[i+1][j] == '#');
                if(f(i+1, j+1)) cnt += (str[i+1][j+1] == '#');
                str[i][j] = toChar(cnt);
            }
        }
    }
    for(int i = 0; i < n; ++i) cout << str[i] << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double[] v = new double[n];
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
        }
        Arrays.sort(v);
        ArrayList<Double> q = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            q.add(v[i]);
        }
        //System.out.println("---");
        while(q.size() > 1) {
            double val = (q.remove(0) + q.remove(0)) / 2;
            //System.out.println(val);
            q.add(val);
            Collections.sort(q);
        }
        System.out.println(q.get(0));
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
#define w(x) int x;cin>>x;while(x--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vll vector<ll>
#define ppi pair<Sint,int>
#define ppl pair<ll,ll>
#define F first
#define S second 
#define LB lower_bound
#define UB upper_bound
#define mset multiset
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll binpow(ll x, ll y, ll p){  ll res = 1;x = x % p;if (x == 0)return 0;while (y > 0)  { if (y & 1) res = (res*x) % p; y = y>>1;x = (x*x) % p;}return res;}  
ll gcd(ll a, ll b){ if (b == 0) return a; return gcd(b, a % b); } 
bool parity(ll x,ll y){ bool f = ((x ^ y) < 0);return !f;}

int main()
{
    IOS

    int n;
    cin>>n;
    vll a(n);
    vll b(n);
    vll c(n);
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];
 
    ll dp[n][3];

    for(int i=0;i<n;i++)
        dp[i][0]=dp[i][1]=dp[i][2]=0;
    
    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[0][2]=c[0];

    for(int i=1;i<n;i++)
    {
        dp[i][0]=dp[i-1][1]>dp[i-1][2]?dp[i-1][1]+a[i]:dp[i-1][2]+a[i];

        dp[i][1]=dp[i-1][0]>dp[i-1][2]?dp[i-1][0]+b[i]:dp[i-1][2]+b[i];

        dp[i][2]=dp[i-1][0]>dp[i-1][1]?dp[i-1][0]+c[i]:dp[i-1][1]+c[i];
    }

    sort(dp[n-1],dp[n-1]+3);
    cout<<dp[n-1][2];

    return 0;

}

Measured memory_bytes: 4992
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto N = readln.chomp.to!int;
    int a, b, ab, r;
    foreach (_; 0..N) {
        auto s = readln.chomp;
        if (s[0] == 'B' && s[$-1] == 'A') {
            ++ab;
        } else if (s[0] == 'B') {
            ++b;
        } else if (s[$-1] == 'A') {
            ++a;
        }
        foreach (i; 0..s.length-1) {
            if (s[i..i+2] == "AB") ++r;
        }
    }

    if (ab > 0) {
        r += ab-1;
        if (a > 0) {
            --a;
            r += 1;
        }
        if (b > 0) {
            --b;
            r += 1;
        }
    }
    r += min(a, b);

    writeln(r);
}

Measured memory_bytes: 380
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <cmath> 
#include <algorithm>
#include <set> 
using namespace std; 
inline int gi() {
    register int data = 0, w = 1;
    register char ch = 0;
    while (!isdigit(ch) && ch != '-') ch = getchar(); 
    if (ch == '-') w = -1, ch = getchar(); 
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
    return w * data; 
}

const int MAX_N = 2e5 + 5; 
struct Node { int x, y; } a[MAX_N]; 
bool operator < (const Node &l, const Node &r) { 
	if (l.x == r.x) return l.y < r.y; 
	else return l.x < r.x; 
} 
int N; 
long long ans = 0; 
multiset<int> s1, s2; 

int main () { 
	N = gi(); 
	for (int i = 1; i <= N; i++) {
		int x = gi(), y = gi(); 
		if (x > y) swap(x, y); 
		a[i] = (Node){x, y}; 
	} 
	sort(&a[1], &a[N + 1]); 
	for (int i = 1; i <= N; i++) s2.insert(a[i].y); 
	ans = 1ll * (a[N].x - a[1].x) * (*s2.rbegin() - *s2.begin()); 
	for (int i = 1; i < N; i++) { 
		s2.erase(s2.find(a[i].y)), s1.insert(a[i].y); 
		int mx1 = *s1.rbegin(), mn1 = *s1.begin(); 
		int mx2 = *s2.rbegin(); 
		int Lmax = max(mx1, a[N].x), Lmin = min(mn1, a[i + 1].x); 
		int Rmax = mx2, Rmin = a[1].x; 
		ans = min(ans, 1ll * (Lmax - Lmin) * (Rmax - Rmin)); 
	} 
	printf("%lld\n", ans); 
    return 0; 
} 

Measured memory_bytes: 11136
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def n_load(p, k, n, w):
    i = 0
    load = 0
    tr = 0
    while i < n:
        if load + w[i] <= p:
            load += w[i]
            i += 1
        else:
            tr += 1
            if tr == k:
                break
            load = 0
    return i

def main():
    n, k = list(map(int, input().strip().split()))
    w = [0] * n
    for i in range(n):
        w[i] = int(input().strip())
    l = 0
    r = INF
    while l +1 < r:
        mid = (l + r) // 2
        ntr = n_load(mid, k, n, w)
        # print('ntr: ', ntr, l, r)
        if ntr == n:
            r = mid
        else:
            l = mid
    print(r)

if __name__ == '__main__':
    main()



Measured memory_bytes: 9416
import sys

K=int(input())
if K==2 or K==3:
  print(K)
elif K==4:
  print(2)
else:
  while True:
    for i in range(2,K//2):
      if K%i!=0:
        if i==(K//2)-1:
          print(K)
          sys.exit()
        continue
      else:
        K=K+1
        break

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

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

  string S, s; cin >> S;
  int Q; cin >> Q;
  int flag = 1;
  for (int i = 0; i < Q; i++) {
    int T; cin >> T;
    if (T == 1) flag = 3 - flag;
    else {
      int F; cin >> F;
      char C; cin >> C;
      if ((flag + F) % 2) S.push_back(C);
      else s.push_back(C);
    }
  }
  if (flag == 2) swap(S, s);
  for (int i = s.size()-1; i >= 0; i--) cout << s[i];
  cout << S << "\n";
}

Measured memory_bytes: 980
#include<iostream>
#include<string>
using namespace std;
int main()
{
	int i, k, len;
	string s;
	cin >> k;
	cin >> s;
	len = s.length();
	for (i = 0; i < k&&i<len; i++) {
		cout << s[i];
	}
	if (k < len) {
		cout << "...";
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 3632
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

const (
	SCANNER_BUF_SIZE = 2 << 20

	INF = int64(math.MaxInt64)
	MOD = 1e9 + 7
)

var (
	writer  *bufio.Writer
	scanner *bufio.Scanner
)

func init() {
	writer = bufio.NewWriter(os.Stdout)
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, SCANNER_BUF_SIZE), SCANNER_BUF_SIZE)
}

func printf(f string, a ...interface{}) {
	fmt.Fprintf(writer, f, a...)
}

func sint64() int64 {
	scanner.Scan()
	bb := scanner.Bytes()
	i := int64(0)
	if bb[0] == '-' {
		for _, b := range bb[1:] {
			i *= 10
			i -= int64(b - '0')
		}
		return i
	}
	for _, b := range bb {
		i *= 10
		i += int64(b - '0')
	}
	return i
}

func suint64() uint64 {
	scanner.Scan()
	bb := scanner.Bytes()
	i := uint64(0)
	for _, b := range bb {
		i *= 10
		i += uint64(b - '0')
	}
	return i
}

func sstring() string {
	scanner.Scan()
	return scanner.Text()
}

func gcd(a, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func lcm(a, b int64) int64 {
	return a * b / gcd(a, b)
}

func abs(a int64) int64 {
	if a < 0 {
		return a * -1
	}
	return a
}

func min(a int64, rest ...int64) int64 {
	for _, r := range rest {
		if r < a {
			a = r
		}
	}
	return a
}

func max(a int64, rest ...int64) int64 {
	for _, r := range rest {
		if r > a {
			a = r
		}
	}
	return a
}

func main() {
	defer writer.Flush()
	n := sint64()
	m := map[string]int64{}
	for ; n > 0; n-- {
		m[sstring()]++
	}
	printf("AC x %d\n", m["AC"])
	printf("WA x %d\n", m["WA"])
	printf("TLE x %d\n", m["TLE"])
	printf("RE x %d\n", m["RE"])
}


Measured memory_bytes: 2532
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static int gcd(int a,int b){
        if(b==0)
            return a;
        int v=a%b;
        return gcd(b,v);
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        int a=sc.nextInt();
        long all=0;
        for(int i=1;i<=a;i++){
            for(int j=1;j<=a;j++){
                for(int k=1;k<=a;k++){
                    if(i==1||j==1||k==1)
                        all+=1;
                    else
                        all+=Main.gcd(Main.gcd(i,j),k);
                }
            }
        }
        System.out.println(all);


    }
}


Measured memory_bytes: 35740
/*#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <array>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
*/

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())

typedef long long ll;
const ll INF = LLONG_MAX - 100;
const ll mod = 2e9 + 7;
const int MAX_N = 5e5 + 5;
int dx[] = { -1LL,0,1LL,0 }, dy[] = { 0,1LL,0,-1LL };
vector<ll> prime;

ll inv[MAX_N], fac[MAX_N];

template <class T = ll> T in() { T x; cin >> x; return (x); }
inline ll GCD(ll a, ll b) { ll c; while (b != 0) { c = a % b; a = b; b = c; }return a; }
inline ll LCM(ll a, ll b) { return a * b / GCD(a, b); }
inline ll POW(ll a, ll b) { ll c = 1LL; while (b > 0) { if (b & 1LL) { c = a * c%mod; }a = a * a%mod; b >>= 1LL; }return c; }
inline void _nCr() { fac[0] = 1LL; for (int i = 1LL; i < MAX_N; i++) { fac[i] = fac[i - 1LL] * i%mod; }for (int i = 0; i < MAX_N; i++) { inv[i] = POW(fac[i], mod - 2); } }
inline ll nCr(ll n, ll r) { return (fac[n] * inv[r] % mod)*inv[n - r] % mod; }
inline void PRI(ll n) { bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) { a[i] = 1LL; }for (int i = 2; i < n + 1LL; i++) { if (a[i]) { prime.pb(i); ll b = i; while (b <= n) { a[b] = 0; b += i; } } } }

typedef pair<int, pair<int, int>> edge;

class UnionFind {
private:
	vector<int> par;
public:
	UnionFind(int N) { par = vector<int>(N, -1LL); }
	int find(int x);
	ll size(int x);
	void unite(int x, int y);
	bool same(int x, int y);
};



class Kruskal {
private:
	UnionFind *uf;
	vector<edge> e;
public:
	vector<edge> mst;
	Kruskal(int N) { uf = new UnionFind(N); }
	void add(int x, int y, ll z);
	void run();
};



//----UnionFind-------------------------------
int UnionFind::find(int x) {
	if (par[x] < 0) return x;
	else return par[x] = find(par[x]);
}

ll UnionFind::size(int x) {
	return -par[find(x)];
}

void UnionFind::unite(int x, int y) {
	x = find(x);
	y = find(y);

	//大きい方に小さい方をくっ付ける
	if (size(x) < size(y)) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

bool UnionFind::same(int x, int y) {
	x = find(x);
	y = find(y);
	return x == y;
}



//----Kruskal-------------------------------
void Kruskal::add(int x, int y, ll z) {
	//x < y
	if (x > y) swap(x, y);
	e.push_back({ z,{x,y} });
}

void Kruskal::run() {
	sort(e.begin(), e.end());
	e.erase(unique(e.begin(), e.end()), e.end());
	for (auto x : e) {
		if (uf->same(x.second.first, x.second.second)) {
			continue;
		}
		else {
			mst.push_back(x);
			uf->unite(x.second.first, x.second.second);
		}
	}
}

int dp[100010][26];

signed main() {
	string s;
	cin >> s;
	FOR (i,1,s.size()) {
		if (s[i] == s[i-1]) {cout << i << " " << i + 1 << endl;return 0;}
	}
	FOR (i,2,s.size()) {
		if (s[i] == s[i-2]) {cout << i-1 << " " << i + 1 << endl;return 0;}
	}
	cout << -1 << " " << -1 << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
string s;
char c;
set<string> st;
int main()
{

	cin >> n;
	cin >> s;
	st.insert(s);
	c = s[(int)s.length() - 1];
	for (int i = 1; i < n; i++) {
		cin >> s;
		if (s[0] != c || st.count(s))
			return !printf("No\n");
		c = s[(int)s.length() - 1];
		st.insert(s);
	}
	printf("Yes\n");
	return 0;

}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		s = s.replaceAll("eraser", "").replaceAll("erase", "").replaceAll("dreamer", "").replaceAll("dream", "");
		System.out.println(s.length() == 0 ? "YES" : "NO");
	}
}


Measured memory_bytes: 33372
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)


def main():
    a,b,c=map(int,input().split())
    g=[list(map(int,input().split()))for i in range(a)]
    h=[list(map(int,input().split()))for i in range(b)]
    for i in zip(*[[sum(s*t for s,t in zip(g[r],[h[j][i]for j in range(b)]))for r in range(a)]for i in range(c)]):
        print(*i)
if __name__ == '__main__':
    main()


Measured memory_bytes: 8372
use std::io::*;
use std::str::FromStr;
use std::cmp::{min, max};
use std::rc::Rc;
use std::mem::swap;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin_lock = stdin.lock();
    let s = stdin_lock
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

static DX: &'static [i32] = &[0, 0, 1, -1];
static DY: &'static [i32] = &[1, -1, 0, 0];

fn dfs(x: usize, y: usize, a: i32, b: i32, dir: usize, map: &Vec<Vec<char>>, gx: usize, gy: usize) -> bool {
    if a < 0 || b < 0 {
        return false;
    }

    if map[y][x] == '#' {
        return false;
    }

    if x == gx && y == gy && a == 0 && b == 0{
        return true;
    }

    let mut ans = false;

    if dir == 0 {
        ans |= dfs(x + 1, y, a, b, 0, &map, gx, gy);
        ans |= dfs(x, y + 1, a, b - 1, 1, &map, gx, gy);
        ans |= dfs(x, y - 1, a - 1, b, 3, &map, gx, gy);
    } else if dir == 1 {
        ans |= dfs(x, y + 1, a, b, 1, &map, gx, gy);
        ans |= dfs(x + 1, y, a - 1, b, 0, &map, gx, gy);
        ans |= dfs(x - 1, y, a, b - 1, 2, &map, gx, gy);
    } else if dir == 2 {
        ans |= dfs(x - 1, y, a, b, 2, &map, gx, gy);
        ans |= dfs(x, y + 1, a - 1, b, 1, &map, gx, gy);
        ans |= dfs(x, y - 1, a, b - 1, 3, &map, gx, gy);
    } else {
        ans |= dfs(x, y - 1, a, b, 3, &map, gx, gy);
        ans |= dfs(x + 1, y, a, b - 1, 0, &map, gx, gy);
        ans |= dfs(x - 1, y, a - 1, b, 2, &map, gx, gy);
    }

    return ans;
}

fn main() {
    let s = read::<String>();

    let mut abc = s.chars().collect::<Vec<char>>();

    abc.sort();

    if abc.into_iter().collect::<String>() == "abc" {
        println!("Yes");
    } else {
        println!("No");
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(m, 0), lag(m-1);
    rep1(i, m) cin >> a[i];
    if (m <= n){
        cout << 0 << endl;
        return 0;
    }
    sort(a.begin(), a.end());
    rep1(i, m){
        lag[i] = abs(a[i+1] - a[i]);
    }
    sort(lag.begin(), lag.end());
    ll ans = 0;
    rep1(i, m-n) ans += lag[i];
    cout << ans << endl;
    //printf("%.12f", ans);
}

Measured memory_bytes: 4676
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] one = {2, 4, 5, 7, 9};
        int[] two = {0, 1, 6, 8};
        int[] three = {3};
        int digit = N % 10;
        if (three[0] == digit) {
            System.out.println("bon");
        } else {
            int flag = 0 ;
            for (int value : two) {
                if (value == digit) {
                    flag = 1;
                    System.out.println("pon");
                    break;
                }
            }
            if( flag == 0 ){
                for (int value : one) {
                    if (value == digit) {
                        System.out.println("hon");
                        break;
                    }
                }
            }
        }
    }
}


Measured memory_bytes: 27032
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define All(a) a.begin(),a.end()
#define INF 1000000007
const int MOD = 1000000007;
//accumulate(vec.begin(), vec.end(), 0)

int gcd(int x,int y){
  if(x%y==0) return y;
  else return gcd(y,x%y);
}

bool isPrime(int n){
  if(n < 2) return false;
  else if(n == 2) return true;
  else if(n%2==0) return false;

  for(int i=3;i<=sqrt(n);i++){
    if(n%i==0) return false;
  }
  return true;
}

int main(){
  ll n;
  cin >> n;
  ll mi = n-1;
  for(ll i=2;i*i<=n;i++){
    if(n%i==0) mi = min(mi,i+n/i-2);
  }
  cout<< mi <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <cstring>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <functional>
#include <ctime>
#include <unordered_map>
#include <sstream>

using namespace std;
typedef long long Long;
typedef long double Double;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
typedef pair<Long,Long> PLL;

int read(int &x) { return scanf("%d", &x); }
int read(int &x, int &y) { return scanf("%d%d", &x, &y); }
int read(int &x, int &y, int &z) { return scanf("%d%d%d", &x, &y, &z); }
int read(Long &x) { return scanf("%lld", &x); }
int read(Long &x, Long &y) { return scanf("%lld%lld", &x, &y); }
int read(double &x) { return scanf("%lf", &x); }
char buff[2000010];
int read(string &s) { int r = scanf("%s", buff); s = buff; return r; }

#define dlog2(n) ((n) == -1 ? 0 : (31-__builtin_clz(n)))

#define sz(a) int(a.size())

struct Point {
	int x,y;
	Point(int x = 0, int y = 0) : x(x), y(y) {}
	double dist(Point o) {
		return sqrt((x-o.x)*(x-o.x) + (y-o.y)*(y-o.y));
	}
};




int main() {

	int N;
	read(N);
	vector<Point> V(N);
	for (auto &p : V) read(p.x, p.y);
	vector<int> I;
	for (int i = 0; i < N; ++i) {
		I.push_back(i);
	}
	double s = 0, c = 0;
	do {
		for (int i = 0; i < I.size() - 1; ++i) {
			s += V[I[i]].dist(V[I[i+1]]);
		}
		c++;
	} while (next_permutation(I.begin(), I.end()));
	printf("%0.10lf\n", s / c);
}
























Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  int cnt = 0;
  int ans = 0;
  cin >> n ;
  vector<int> h(n) ;
  cin >> h[0];
  for(int i = 0;i < n-1;i++){
    cin >> h[i+1];
      if(h[i+1]<=h[i])
      {
        cnt ++;
        ans = max(ans, cnt);
      }else{
        cnt = 0;
      }    
  }
  cout << ans << "\n" ;
  return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
	int A, B, C, K;
	cin >> A >> B >> C >> K;

	if (K % 2 == 1) cout << B - A;
	else cout << A - B;


    return 0;
}


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

int main() {
    
    int N;
    cin >> N;
    
    vector<string> s(N);
    for (int i = 0; i < N; i++)
    {
        cin >> s[i];
        sort(s[i].begin(), s[i].end());
    }

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

    long long ans = 0;
    int count = 0;
    for (int i = 1; i < N; i++)
    {
        if (s[i] == s[i-1]) {
            count++;
            ans += count;
        }
        else {
            count = 0;
        }
    }

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



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


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define pb push_back
#define mp make_pair
#define snd second
#define fst first
#define debug printf("--%d--\n",__LINE__)
#define ll long long int

int x, p;
int main(void){
	cin >> x >> p;
	int n = (abs(x)+1)/2;
	int q = ((x>0) ? p : 100-p);
	double pr = 0.01 * q;
	printf("%.8f\n", n / pr);
	
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define pll pair <long long, long long>
#define fi first
#define sc second
#define ALL(x) x.begin(), x.end()
#define RALL(X) x.begin(), x.end()
#define FOR(i, n, k) for(i=0; i<n; i+=k)
#define FO(i, n, k) for(i=1; i<=n; i+=k)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define N 100005
#define mid ((l+r)/2)
#define dbg(x) (cerr << #x << " : " << x << endl)
#define endl "\n"
#define MOD 100000009

using namespace std;

typedef long long int lli;

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	lli res = 0;
	vector <lli> ar(n);
	for(lli &x: ar){
		cin >> x;
		res += x;
	}
	sort(ALL(ar));
	
	vector <pll> que;
	for(int i=0; i<m; i++){
		lli b, c;
		cin >> b >> c;
		que.pb(mp(c, b));
	}
	sort(ALL(que), greater<pll>());

	int idx=0;
	
	for(int i=0; i<m and idx<n; i++){
		pll q = que[i];
		for(int j=0; j<q.sc and idx<n; idx++, j++){
			if(ar[idx] < q.fi){
				res -= ar[idx];
				res += q.fi;
			}
		}
	}

	cout << res;
	return 0;
}

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

const int dh[4] = {0,1,0,-1};
const int dw[4] = {1,0,-1,0};

int main(void){
    int H,W;
    cin >> H >> W;
    vector<string> field(H);
    int originblack = 0;    //もともと黒のマス数
    for(int i=0;i<H;i++){
        cin >> field[i];
        for(int j=0;j<W;j++){
            if(field[i][j]=='#') originblack++;
        }
    }

    vector<vector<int>> dist(H,vector<int>(W,-1));
    queue<pair<int,int>> q;
    q.push(make_pair(0,0));
    dist[0][0] = 0;

    bool goal = false;
    while(!q.empty()){
        pair<int,int> pos = q.front(); q.pop();
        int h = pos.first, w = pos.second;

        for(int k=0;k<4;k++){
            int nh = h+dh[k], nw = w+dw[k];

            if(nh<0||nh>=H||nw<0||nw>=W) continue;
            if(field[nh][nw]=='#') continue;
            if(dist[nh][nw]!=-1) continue;

            dist[nh][nw] = dist[h][w] + 1;
            if(nh==H-1 && nw==W-1){
                goal = true;
            }
            q.push(make_pair(nh,nw));
        }
    }

    if(goal) cout << H*W - dist[H-1][W-1] - 1 - originblack << endl;
    else cout << -1 << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int A,B,C;
  cin >> A >> B >> C ;

  if(A == B){
    cout << C << endl;
  }

  if(B == C){
    cout << A << endl;
  }
  
  if(C == A){
    cout << B << endl;
  }

}

Measured memory_bytes: 256
n,a,b=map(int,input().split())
mod=10**9+7
maxx=pow(2,n,mod)-1


res=0
pat=1
for i in range(0,n+1):
  res=pat
  if i==a:
    maxx-=res
  if i==b:
    maxx-=res
    break
  #res=patとすれば,print(res)でnCkが求まる
  pat*=(n-i)*pow(i+1,mod-2,mod)
  pat%=mod
  
print(maxx%mod)

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

typedef long long int ll;
typedef string str;

int main ()
{
	// ios::sync_with_stdio(0);
 //    cin.tie(0);
 //    cout.tie(0);
	ll t,n,m,k,i,a,b,j;
	cin >> n >> m;
	k=n*(n-1) + m*(m-1);
	k/=2;
	cout << k << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n,c=0;
  cin>>n;
  vector<ll> a(n+1);
  for(ll i=0;i<n;i++){
    cin>>a[i];
  }
  a[n]=0;
  for(ll i=0;i<n;i++){
    if(a[i]>1){
      c+=a[i]/2;
      a[i]-=a[i]/2*2;
    }
    if(a[i]==1){
      if(a[i+1]>0){
        c++;
        a[i]--;
        a[i+1]--;
      }
    }
  }
  cout<<c<<endl;
}

Measured memory_bytes: 1024
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [10**10 for i in range(N+1)]
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    for j in range(max(1, i-K+1), i+1):
        if dp[i] >= dp[j-1] + abs(h[i]-h[j-1]):
            dp[i] = dp[j-1] + abs(h[i]-h[j-1])

print(dp[N-1])
#print(dp)

Measured memory_bytes: 56544
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
1 4 2 5 3
ニムトみたいな。一番大きい数の後ろにくっつけてくかんじ
配列すごいたくさん用意する？
1 4 2 5 3
1
4
2 4
2 5
3 5
=2
multisetで、上書きってできんのかな
それできたらいけそう
setの上書きできないのか
vectorならできんの？

あああこれ天才だな。
0判定するために+1の値をおさめてく。
00003
00023
00025
00026
00046
2

*/
int main(){
  ll N; cin>>N;
  vector<ll> M(N,0);
  for(ll i=0; i<N; i++){
    ll a; cin>>a;
    a++;
    auto IT=lower_bound(M.begin(), M.end(), a);
    IT--;//a=2 2未満を満たす最短箇所+1を指し示すぽい。なんで？
    *IT=a;
  }
  cout<<M.end()-lower_bound(M.begin(), M.end(), 1)<<endl;
}

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

//#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LONG_LONG_MAX


int main(){
    int n;
    cin>> n;
    int t=n;
    int co=1;
    int cg=1;
    int su=0;
    while(t>0){
        t=t/10;
        if (t>0 & cg%2!=0){
            su+=co*9;
        }
        co*=10;
        cg+=1;
        if(t==0 & cg%2==0){
            su+=n-(co/10)+1;
        }
    }
    cout <<su << endl;
}
    

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <set>
#include <vector>
#include <map>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <climits>
#include <numeric>
#include <sstream>
using namespace std;
typedef long long ll;
#define DEBUG
#ifdef DEBUG
	#define debug printf
#else
	#define debug(...)
#endif
const int maxn = 1e5 + 50;
set<ll> ans;
void bfs()
{
	priority_queue< ll,vector<ll>,greater<ll> > pq;
	for(int i = 1;i <= 9; ++i)
	{
		pq.push(i);
	}
	while(!pq.empty() && (ans.size() < (1e5 + 10)))
	{
		ll now = pq.top();
		pq.pop();
		ans.insert(now);
		int l = max(0ll,now % 10 - 1);
		int r = min(9ll,now % 10 + 1);
		for(int i = l;i <= r; ++i)
		{
			pq.push(now * 10 + i);
		}
	}
}
int main(int argc, char const *argv[])
{
	bfs();
	ll k;
	scanf("%lld",&k);
	set<ll>::iterator iter = ans.begin();
	while(--k)
	{
		// printf("%lld\n",*iter);
		++iter;
	}
	printf("%lld\n",*iter);
	return 0;
}

Measured memory_bytes: 6384
#include <atcoder/all>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using namespace atcoder;
int op(int a, int b) { return max(a, b); }
int e() { return -1; }
int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	segtree<int, op, e> dp(300010);
	// dp[a]:=最後がaであるのの最長の長さ
	for (int i = 0; i < n; i++) {
		int ai = a[i];
		int dai = dp.get(ai);
		int low = ai - k;
		int hi = ai + k;
		low = max(low, 0);
		hi = min(hi, 300008);
		int num = dp.prod(low, hi + 1);
		if (num >= 1) {
			dai = max(dai, 1 + num);
		}
		dai = max(dai, 1);
		dp.set(ai, dai);
	}
	cout << dp.all_prod() << endl;
	return 0;
}

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

#define ll long long
#define siz 100005
typedef pair<int ,int> pii;

int main(){

    ios_base::sync_with_stdio(0);
    //freopen("overcode.in","r",stdin);
    //freopen("out.txt","w",stdout);


    int n,w;
    ll wei[105],val[105];
    ll dp[105][100005]={0};

    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>wei[i]>>val[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){
            if(wei[i]>j) dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]);
        }
    }

    cout<<dp[n][w];


    return 0;
}


Measured memory_bytes: 82304
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using P = pair<int, int>;
using ll = long long;
 
int main(){
	int n;
  	cin >> n;
  	vector<int> a(n);
	rep(i, n) cin >> a[i];
 	int nxt = 1, ans = 0;
  	rep(i, n){
    	if(a[i] == nxt){
            nxt++;
        } else ans++;
    }
  		
  	if(ans == n) ans = -1;
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};


bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  ll l=0,r=0,N,A[200001],sum=0,now=0;
  cin >> N;
  REP(i,N)cin >> A[i];
  while(r < N){
    if((A[r] ^ now) == (A[r] + now)){
      now = now^A[r];
      r++;
      sum += r-l;
    }else{
      now = now^A[l];
      l++;
    }
  }
  cout << sum << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
const int MOD = 1000000007;
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


Measured memory_bytes: 1792
import numpy as np
import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        S = [0 if c == '#' else 1 for c in input().strip()]
        A.append(S)

    A = np.array(A)
    up = np.zeros((H+1, W), dtype=np.int)
    down = np.zeros((H+1, W), dtype=np.int)
    right = np.zeros((H, W+1), dtype=np.int)
    left = np.zeros((H, W+1), dtype=np.int)

    for i in range(1, H+1):
        up[i] = (up[i-1] + 1) * A[i-1]

    for i in range(H-1, -1, -1):
        down[i] = (down[i+1] + 1) * A[i]

    for i in range(1, W+1):
        right[:, i] = (right[:, i-1] + 1) * A[:, i-1]

    for i in range(W-1, -1, -1):
        left[:, i] = (left[:, i+1] + 1) * A[:, i]

    R = (up[1:] + down[:H] - 1) * A
    C = (right[:, 1:] + left[:, :W] - 1) * A
    W = (R + C - 1) * A
    return W.max()


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 326060
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;


int main(void){
   long long N,K;
   cin>>N>>K;
   vector<int> A(N);
   for(int i=0;i<N;i++){
      cin>>A[i];
      A[i]--;
   }
   int now=0;
   vector<int> count(N,0);
   long long roop_town,rest;
   bool flag=false;
   for(int i=0;i<K;i++){
      now=A[now];
      if(count[now]!=0){
         roop_town=i-count[now];
         rest=K-i-1;
         flag=true;
         break;
      }
      count[now]=i;
   }
   if(flag){
      rest=rest%roop_town;
      for(int j=0;j<rest;j++){
         now=A[now];
      }
   }
   cout<<now+1<<endl;
   return 0;
}

Measured memory_bytes: 4844
def gen_lunlun(stop, base=[1, 2, 3, 4, 5, 6, 7, 8, 9]):
    if stop <= 0:
        return base
    
    new_lunlun = []
    for x in base:
        lank1 = x%10
        b = x*10+lank1
        if lank1 == 0:
            tmp = [b, b+1]
        elif lank1 == 9:
            tmp = [b-1, b]
        else:
            tmp = [b-1, b, b+1]
        new_lunlun.extend(tmp)
        if len(new_lunlun) >= stop:
            break
    base.extend(gen_lunlun(stop-len(new_lunlun), new_lunlun))
    return base

k = int(input())
print(gen_lunlun(k-9)[k-1])

Measured memory_bytes: 8824
package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	read  = bufio.NewReader(os.Stdin)
	write = bufio.NewWriter(os.Stdout)
)

func main() {
	defer write.Flush()

	var h, a int
	fmt.Fscan(read, &h, &a)

	fmt.Fprintln(write, (h+a-1)/a)
}


Measured memory_bytes: 640
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author NikuKyabe
 */

#include <iostream>
#include <fstream>

#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#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 ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " <<
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

class CWelcomeToAtCoder {
public:
	void solve(std::istream& in, std::ostream& out) {
    int n,m;
    in >> n >> m;
    vector<pair<int, string>> ps(m);
    REP(i,m) {
      in >> ps[i].first >> ps[i].second;
      ps[i].first--;
    }
    vec memo(n,0);
    vector<bool> isAC(n,false);
    REP(i,m){
      if(!isAC[ps[i].first] && ps[i].second == "WA"){
        memo[ps[i].first]++;
      }
      else{
        isAC[ps[i].first] = true;
      }
    }
    vec ans(2, 0);
    REP(i,n){
      ans[0] += isAC[i] ? 1 : 0;
      ans[1] += isAC[i] ? memo[i] : 0;
    }
    out << ans[0] SP ans[1] << endl;
	}
};


signed main() {
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout.precision(20);
	CWelcomeToAtCoder solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

using namespace std;

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

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    for (auto a: v)
        out << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename S, typename T>
ostream& operator<<(ostream& out, const map<S, T>& M) {
    for (auto m: M)
        cout << "(" << m.first << "->" << m.second << ") ";
    return out;
}

template<typename S, typename T>
pair<S, T> operator+(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first + b.first, a.second + b.second);
}

template<typename S, typename T>
pair<S, T> operator-(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first - b.first, a.second - b.second);
}

void solve() {
    string str;
    cin >> str;
    for (auto &ch: str) {
        if (ch == '?') {
            ch = 'D';
        }
    }
    cout << str << endl;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 3772
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{

	ll X,Y,t,tt=1,r=1;
	cin>>X>>Y;
	t=Y/X;
	while(tt<=t)
	{
		r++;
		tt*=2;
	}
	cout<<r-1<<endl;
}


Measured memory_bytes: 256
#include<iostream>

int main()
{
	int a, b;
	char op;
	
	while(std::cin >> a >> op >> b) {
		if(op == '?') break;

		int answer;
		if(op == '+') {
			answer = a + b;
		} else if(op == '-') {
			answer = a - b;
		} else if(op == '*') {
			answer = a * b;
		} else if(op == '/') {
			answer = a / b;
		}
		std::cout << answer << '\n';
	}

	return 0;
}
		

Measured memory_bytes: 1160