akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    string S;cin >> S;
    string maerd = "maerd";
    string remaerd = "remaerd";
    string esare = "esare";
    string resare = "resare";
    int ed = S.size()-1;
    int itr = ed;
    bool ok = true;
    while(ok){
        if(itr < 0)break;

        if(S[itr] == 'm'){
            if(itr >= 4){
                rep(i,5){
                    if(S[itr-i] != maerd[i])ok = false;
                }
                itr -= 5;
            }
            else{
                ok = false;
            }
        }
        else if(S[itr] == 'r'){
            if(itr >= 5){
                if(S[itr-2] == 'm'){
                    if(itr >= 6){
                        rep(i,7){
                            if(S[itr - i] != remaerd[i])ok = false;
                        }
                        itr -= 7;
                    }
                    else{
                        ok = false;
                        break;
                    }
                }
                else if(S[itr-2] == 's'){
                    rep(i,6){
                        if(S[itr-i] != resare[i])ok = false;
                    }
                    itr -= 6;
                }
                else {
                    ok = false;
                    break;
                }
            }
            else {
                ok = false;
            }
        }
        else if(S[itr] == 'e' ){
            if(itr >= 4){
                rep(i,5){
                    if(S[itr-i] != esare[i])ok = false;
                }
                itr -= 5;
            }
        }
        else {
            ok = false;
            break;
        }
    }
    if(ok)cout << "YES" << endl;
    else cout << "NO" <<endl;
}



Measured memory_bytes: 764
#include<cstdio>
#include<vector>
const int MAX = 1e5;

long long K;
std::vector<long long> num(MAX + 1);

int main() {
	int a, b, N;
	scanf("%d %lld\n", &N, &K);

	for (int i = 0; i < N; i++) {
		scanf("%d %d", &a, &b);
		num[a] += b;
	}

	for (int i = 1; i <= MAX; i++) {
		if (K <= num[i]) {
			printf("%d\n", i);
			return 0;
		}
		K -= num[i];
	}
}


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

int yarudake(int x){
    if(x%10!=0){x = 10*(x/10+1);}
    return x;
}

int main(){
    int a,b,c,d,e;
    cin >>a>>b>>c>>d>>e;
    int f=10;
    if(a%10!=0) f=a;
    if(c%10!=0&&c%10<f%10) f=c;
    if(d%10!=0&&d%10<f%10) f=d;
    if(b%10!=0&&b%10<f%10) f=b;
    if(e%10!=0&&e%10<f%10) f=e;
    
    a=yarudake(a);
    b=yarudake(b); 
    c=yarudake(c); 
    d=yarudake(d); 
    e=yarudake(e);
    int ans = a+b+c+d+e;
    //cout<<ans <<endl;
    if(f!=10){
        ans-= 10*(f/10+1);
        ans+=f;
    }
    
    cout <<ans<<endl;
    
    

}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string A, B, C;
  cin >> A >> B >> C;
  int a = A.size();
  int b = B.size();
  int c = C.size();
  char a2 = A.at(a - 1);
  char b1 = B.at(0);
  char b2 = B.at(b - 1);
  char c1 = C.at(0);
  if (a2 == b1){
    if(b2 == c1){
      cout << "YES" << endl;
    }
    else {
      cout << "NO" << endl;
    }
  }
  else {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
import java.util.*;
import java.util.function.*;
import java.math.*;
public class Main {
    public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		char[] str1 = s.next().toCharArray();
		char[] str2 = s.next().toCharArray();
		
		if(str1.length > str2.length) {
			char[] tmp = str1;
			str1 = str2;
			str2 = tmp;
		}
		
		int[][] dp = new int[3000][3000];
		
		dp[0][0] = str1[0] == str2[0] ? 1: 0;
		
		for(int i = 1; i < str2.length; i++) {
			if(str1[0] == str2[i]) {
				dp[0][i] = 1;
			}else {
				dp[0][i] = dp[0][i-1];
			}
		}
		for(int i = 1; i < str1.length; i++) {
			if(str2[0] == str1[i]) {
				dp[i][0] = 1;
			}else {
				dp[i][0] = dp[i-1][0];
			}
		}
		
		for(int i = 1; i < str1.length; i++) {
			for(int j = 1; j < str2.length; j++) {
				if(str1[i]==str2[j]) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}else {
					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
				}
			}
		}
		
		StringBuilder ret = new StringBuilder();
		int i = str1.length - 1;
		int j = str2.length - 1;
		while(i >= 0 && j >= 0) {
			if(str1[i] == str2[j]) {
				ret.insert(0, str1[i]);
				--i;--j;
			}else {
				if(i < 1) {
					j--;
				}else if(j < 1) {
					i--;
				}
				else if(dp[i-1][j] > dp[i][j-1]) {
					--i;
				}else {
					--j;
				}
			}
		}
		System.out.println(ret.toString());
    }
}


Measured memory_bytes: 80208
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( stdin . lock ( ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , mut $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let mut $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

fn main() {
    input! {
        a: chars, b: chars, c: chars
    }
    println!("{}", if a[a.len()-1] == b[0] && b[b.len()-1] == c[0] {"YES"} else {"NO"});
}

Measured memory_bytes: 4352
/*Allah Vorosha*/
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define n_p next_permutation
#define p_p prev_permutation
#define in insert
#define rev reverse
#define pf push_front
#define pob pop_back
#define uniq(v)         v.resize(distance(v.begin(),unique(v.begin(),v.end())))
#define all(x) (x).begin(),(x).end()
#define pof pop_front
#define ios ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define scn scanf
#define prt printf
#define rep(i, a, n) for(int i = a; i < n; i++)
#define mod 1000000007
#define yes cout << "YES\n"
#define no cout << "NO\n";
#define take for(auto &it : a) cin >> it;
#define out cout << a << "\n";
#define l_b lower_bound
#define u_b upper_bound
#define Max 100005
template<typename T> T mymax(T x, T y) {
    return (x > y ? x : y);
}

using namespace std;

const int N = 2e5 + 5;

ll lcm (ll c, ll d) {
    return (c * d) / (__gcd(c, d));
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), pre_gcd(n), suf_gcd(n);
    take;
    pre_gcd[0] = a[0];
    suf_gcd[n - 1] = a[n - 1];
    int ans = 0;
    for(int i = 1; i < n; i++) pre_gcd[i] = __gcd(a[i], pre_gcd[i - 1]);
    for(int i = n - 2; i >= 0; i--) suf_gcd[i] = __gcd(suf_gcd[i + 1], a[i]);
    for(int i = 0; i < n; i++) {
        if(i - 1 >= 0 && i + 1 < n) {
            ans = max(ans, __gcd(pre_gcd[i - 1], suf_gcd[i + 1]));
        }
        if(i == 0) {
            ans = max(ans, suf_gcd[i + 1]);
        }
        if(i + 1 == n) {
            ans = max(ans, pre_gcd[i - 1]);
        }
    }
    cout << ans << '\n';
}

int main() {

    solve();
    return 0;
}


Measured memory_bytes: 4576
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define veci vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vec>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))


using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
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;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
template<class T> inline void print(T v){for(auto e:v)cout<<e<<" ";cout<<endl;}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x:vec) is >> x;
    return is;
}
const ll INF=1e9+100;

int main()
{
    ll n,k;
    cin >> n >> k;
    vector<double> a(1000);
    rep(i,1000){
        a[i]=i+1;
    }
    vector<double> s(1000);
    s[0]=a[0];
    rep(i,1000){
        if(i==0){
            continue;
        }
        s[i]=s[i-1]+a[i];
    }
    vector<double> p(n);
    vector<double> q(n);
    rep(i,n){
        cin >> p[i];
        q[i]=s[p[i]-1]/p[i];
        //cout << q[i] << endl;
    }
    vector<double> ss(n);
    ss[0]=q[0];
    rep(i,n){
        if(i==0){
            continue;
        }
        ss[i]=ss[i-1]+q[i];
        //cout << ss[i] << endl;
    }
    double ans=-1;
    rep(i,n-k+1){
        if(i==0){
            ans=max(ans,ss[k-1]);
        }
        else{
            ans=max(ans,ss[i+k-1]-ss[i-1]);
        }
    }
    cout << setprecision(30) << fixed;
    cout << ans << endl;
    return 0;
} 

Measured memory_bytes: 4992
using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		String s="";
		while((s=Console.ReadLine())!=null){
			if(s=="END")break;
			Sol mySol =new Sol(s);
			mySol.Solve();
		}
	}
}

class Sol{
	public void Solve(){
		
		char[] cs=S.ToCharArray();
		for(int i=0;i<cs.Length;i++){
			if(cs[i]>='1' && cs[i]<='9'){
				cs[i]=In[cs[i]-'0'];
			}
		}
		
		
		ans=0;
		dfs(cs);
		Console.WriteLine(ans);
	}
	
	int ans;
	
	
	void dfs(char[] cs_){
		char[] cs=new Char[cs_.Length];
		int pibot=-1;
		for(int i=0;i<cs.Length;i++){
			cs[i]=cs_[i];
			if(cs[i]==' ')pibot=i;
		}
	
		if(pibot==-1){
			String expr=new String(cs);
			String sc=ParseAndCalc(expr);
			if(sc=="F")ans++;
			return;
		}
	
		//dfs all operator
		cs[pibot]='a';
		dfs(cs);
		cs[pibot]='o';
		dfs(cs);
		cs[pibot]='e';
		dfs(cs);
		cs[pibot]=' ';
	}
	
	
	String ParseAndCalc(String expr){
		String ret=expr;
		bool chk=true;
		
		while(chk){
			chk=false;
			int i;
			//まずかっこを処理
			for(i=0;i<ret.Length;i++){
				if(ret[i]=='('){
					chk=true;
					break;
				}
			}
			if(chk){
				int depth=1;
				int j=i;
				while(depth!=0){
					j++;
					if(ret[j]=='(')depth++;
					if(ret[j]==')')depth--;
				}
				var s=ret.Substring(i+1,j-i+1-2);
				ret=ret.Substring(0,i)+ParseAndCalc(s)+ret.Substring(j+1);
				continue;
			}
		
			//演算子を処理
			for(i=0;i<ret.Length;i++){
				if(ret[i]=='a'||ret[i]=='o'||ret[i]=='e'){
					chk=true;
					break;
				}
			}
			if(chk){
				int l=H2I[ret[i-1]];
				int r=H2I[ret[i+1]];
	
				int res=0;
				if(ret[i]=='a')res=l&r;
				if(ret[i]=='o')res=l|r;
				if(ret[i]=='e')res=l^r;
				
				char c=I2H[res];
				ret=c.ToString();
			}
		}
		
		return ret;
	
	}
	
	String S;
	Dictionary<char,int> H2I;
	char[] I2H;
	
	int N;
	char[] In;
	
	public Sol(String s){
		S=s;
		
		H2I=new Dictionary<char,int>();
		for(char c='0';c<='9';c++){
			H2I.Add(c,(int)(c-'0'));
		}
		for(char c='A';c<='F';c++){
			H2I.Add(c,10+(int)(c-'A'));
		}
		
		I2H=new char[16];
		for(int i=0;i<16;i++){
			if(i<10)I2H[i]=(char)('0'+i);
			if(i>9)I2H[i]=(char)('A'+i-10);
		}
		
		N=ri();
		In=new char[N+1];
		In[0]='x';
		for(int i=1;i<=N;i++){
			var d=ria();
			int ii=0;
			for(int j=0;j<4;j++){
				ii=ii|(d[j]<<j);
			}
			In[i]=I2H[ii];
		}
		
	}




	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}

Measured memory_bytes: 6356
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

int pnt = 3;

vector<tuple<int, int, int, int>> out;

int op(int type, int i, int j) {
	out.push_back(make_tuple(type, i, j, pnt));
	pnt++;
	return pnt - 1;
}

int ONE = -1;
vector<int> PWS;

vector<int> make_bits(int POS) {
	int plus_one = op(0, POS, ONE);
	vector<int> bits(32);
	int cur = op(0, pnt, pnt);
	for (int i = 31; i >= 0; i--) {
		int cur_add = op(0, cur, PWS[i]);
		int cur_less = op(1, cur_add, plus_one);
		bits[i] = cur_less;
		for (int j = 0; j < i; j++) {
			cur_less = op(0, cur_less, cur_less);
		}
		cur = op(0, cur, cur_less);
	}
	return bits;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int some_bigger = op(0, 0, 1);
	some_bigger = op(0, some_bigger, some_bigger);
	ONE = op(1, 0, some_bigger);
	PWS = {ONE};
	for (int i = 1; i < 32; i++) {
		PWS.push_back(op(0, PWS.back(), PWS.back()));
	}
	vector<int> bits_a = make_bits(0);
	vector<int> bits_b = make_bits(1);
	//in bits_a all 
	//0 -> 0
	//1 -> b
	for (int i = 0; i < 32; i++) {
		vector<int> and_bits(32);
		for (int j = 0; j < 32; j++) {
			int sm = op(0, bits_a[i], bits_b[j]);
			and_bits[j] = op(1, ONE, sm);
		}
		int C = op(0, pnt, pnt);
		for (int j = 31; j >= 0; j--) {
			C = op(0, C, C);
			C = op(0, C, and_bits[j]);
		}
		bits_a[i] = op(0, 2, C);
	}
	int C = op(0, pnt, pnt);
	for (int i = 31; i >= 0; i--) {
		C = op(0, C, C);
		C = op(0, C, bits_a[i]);
	}
	out.push_back(make_tuple(0, 2, C, 2));
	cout << out.size() << endl;
	for (auto x : out) {
		if (!get<0>(x)) {
			cout << "+ ";
		} else {
			cout << "< ";
		}
		cout << get<1>(x) << ' ' << get<2>(x) << ' ' << get<3>(x) << '\n';
	}
}

Measured memory_bytes: 3132
#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.at(i) != t.at(i)){
      ans++;
    }
  }
  
  cout << ans << endl;
}
  

Measured memory_bytes: 3836
#include<cstdio>
#include<iostream>
int m,n,k;
int jh[1000][1000]={},jw[1000][1000]={},oh[1000][1000]={},ow[1000][1000]={},ih[1000][1000]={},iw[1000][1000]={};
char field[1000][1000];

void solve_ac(int a,int b,int c,int d){
	//printf("ac:call %d,%d,%d,%d\n",a,b,c,d);
	int j=0,o=0,i=0;
	if(a==0){
		for(int lp=b;lp<=d;lp++){
			j+=jw[c][lp];
			o+=ow[c][lp];
			i+=iw[c][lp];
		}
	}else{
		for(int lp=b;lp<=d;lp++){
			j+=jw[c][lp]-jw[a-1][lp];
			o+=ow[c][lp]-ow[a-1][lp];
			i+=iw[c][lp]-iw[a-1][lp];
		}
	}
	printf("%d %d %d\n",j,o,i);
}
void solve_bd(int a,int b,int c,int d){
	//printf("bd:call %d,%d,%d,%d\n",a,b,c,d);
	int j=0,o=0,i=0;
	if(b==0){
		for(int lp=a;lp<=c;lp++){
			j+=jh[lp][d];
			o+=oh[lp][d];
			i+=ih[lp][d];
		}
	}else{
		for(int lp=a;lp<=c;lp++){
			j+=jh[lp][d]-jh[lp][b-1];
			o+=oh[lp][d]-oh[lp][b-1];
			i+=ih[lp][d]-ih[lp][b-1];
		}
	}
	printf("%d %d %d\n",j,o,i);
}
int main(void){
	int a,b,c,d;
	char temp;
	scanf("%d %d %d",&m,&n,&k);
	for(int lp_h=0;lp_h<m;lp_h++){
		for(int lp_w=0;lp_w<n;lp_w++){
			scanf("%c",&temp);
			if(temp=='\n'){
				lp_w--;
			}else{
				field[lp_h][lp_w]=temp;
			}
		}
	}
	for(int lp_h=0;lp_h<m;lp_h++){
		if(field[lp_h][0]=='J'){
			jh[lp_h][0]=1;
		}else if(field[lp_h][0]=='O'){
			oh[lp_h][0]=1;
		}else{
			
			ih[lp_h][0]=1;
		}
		for(int lp_w=1;lp_w<n;lp_w++){
			if(field[lp_h][lp_w]=='J'){
				jh[lp_h][lp_w]=1;
			}else if(field[lp_h][lp_w]=='O'){
				oh[lp_h][lp_w]=1;
			}else{
				ih[lp_h][lp_w]=1;
			}
			jh[lp_h][lp_w]+=jh[lp_h][lp_w-1];
			oh[lp_h][lp_w]+=oh[lp_h][lp_w-1];
			ih[lp_h][lp_w]+=ih[lp_h][lp_w-1];
		}
	}
	//printf("field make comp\n");
	/*for(int lp_h=0;lp_h<m;lp_h++){
		for(int lp_w=0;lp_w<n;lp_w++){
			printf("%d ",jh[lp_h][lp_w]);
		}
		printf("\n");
	}
	*/
	for(int lp_w=0;lp_w<n;lp_w++){
		if(field[0][lp_w]=='J'){
			jw[0][lp_w]=1;
		}else if(field[0][lp_w]=='O'){
			ow[0][lp_w]=1;
		}else{
			iw[0][lp_w]=1;
		}
		for(int lp_h=1;lp_h<m;lp_h++){
			if(field[lp_h][lp_w]=='J'){
				jw[lp_h][lp_w]=1;
			}else if(field[lp_h][lp_w]=='O'){
				ow[lp_h][lp_w]=1;
			}else{
				iw[lp_h][lp_w]=1;
			}
			jw[lp_h][lp_w]+=jw[lp_h-1][lp_w];
			ow[lp_h][lp_w]+=ow[lp_h-1][lp_w];
			iw[lp_h][lp_w]+=iw[lp_h-1][lp_w];
		}
		
	}
	/*for(int lp_h=0;lp_h<m;lp_h++){
		for(int lp_w=0;lp_w<n;lp_w++){
			printf("%d ",jw[lp_h][lp_w]);
		}
		printf("\n");
	}*/
	//printf("fielddp comp\n");
	for(int lp=0;lp<k;lp++){
		//printf("loopstart\n");
		scanf("%d %d %d %d",&a,&b,&c,&d);
		if(c-a>d-b){
			solve_ac(a-1,b-1,c-1,d-1);
		}else{
			solve_bd(a-1,b-1,c-1,d-1);
		}
	}
	
	return 0;
	
}

Measured memory_bytes: 27312
// https://atcoder.jp/contests/abc116/tasks/abc116_d
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define EPS (1e-9)
#define INF (1e9)
#define INFL (1e18)
#define MOD (1000000007)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

template <int mod> struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) {
        if ((x = x_ % mod + mod) >= mod)
            x -= mod;
    }
    ModInt &operator+=(ModInt rhs) {
        if ((x += rhs.x) >= mod)
            x -= mod;
        return *this;
    }
    ModInt &operator-=(ModInt rhs) {
        if ((x -= rhs.x) < 0)
            x += mod;
        return *this;
    }
    ModInt &operator*=(ModInt rhs) {
        x = (unsigned long long)x * rhs.x % mod;
        return *this;
    }
    ModInt &operator/=(ModInt rhs) {
        x = (unsigned long long)x * rhs.inv().x % mod;
        return *this;
    }
    ModInt operator-() const { return -x < 0 ? mod - x : -x; }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    ModInt inv() const { return pow(*this, mod - 2); }
    friend ostream &operator<<(ostream &s, ModInt<mod> a) {
        s << a.x;
        return s;
    }
    friend istream &operator>>(istream &s, ModInt<mod> &a) {
        s >> a.x;
        return s;
    }
};
using mint = ModInt<(int)1e9 + 7>;

mint dp[101][8];

// フィボナッチ数列
double fib(int n) {
    double phi = (sqrt(5) + 1) / 2.0;
    return round(pow(phi, n) / sqrt(5));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w, k;
    cin >> h >> w >> k;
    vector<ll> fib(10);
    fib[0] = 1;
    fib[1] = 1;
    FOR(i, 2, 10) fib[i] = fib[i - 1] + fib[i - 2];
    dp[0][1] = 1;
    REP(i, h) FOR(j, 1, w + 1) {
        if (j >= 2) {
            dp[i + 1][j - 1] += dp[i][j] * (fib[j - 2] * fib[w - j]);
        }
        if (j <= w - 1) {
            dp[i + 1][j + 1] += dp[i][j] * (fib[j - 1] * fib[w - j - 1]);
        }
        dp[i + 1][j] += dp[i][j] * (fib[j - 1] * fib[w - j]);
    }
    cout << dp[h][k] << endl;

    return 0;
}


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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  vector<char> v(52);
  rep(i,26) v[i]='a'+i;
  rep(i,26) v[i+26]='A'+i;
  map<char,int> mp;
  rep(i,52) mp[v[i]]=i;
  while(1){
    int n;
    cin >> n;
    if(n==0) return 0;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    string s;
    cin >> s;
    int m = s.length();
    rep(i,m){
      s[i]=v[(mp[s[i]]-a[i%n]+52)%52];
    }
    cout << s << endl;
  }
  return 0;
}



Measured memory_bytes: 3200
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define N 100005
#define M 100005
struct node{
	int u,v;
}edge[M],ans[M];
int n,m,cnt;
vector<int>G[N],T[N];
bool vis[M];
//bool vis[N];
int d[N],ft[N];
int rt=-1;
/*void dfs(int u,int f)
{
	vis[u]=1;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(vis[v]||v==f) continue;
		T[u].push_back(v);
		T[v].push_back(u);
		dfs(v,u);
	}
}*/
int Find(int x)
{
	if(ft[x]==x)
		return x;
	return ft[x]=Find(ft[x]);
}
bool Union(int x,int y)
{
	int u=Find(x),v=Find(y);
	if(u==v) return 0;
	if(u>v) ft[u]=v;
	else ft[v]=u;
	return 1;	
}
void dfs2(int u,int f)
{
	//printf("%d\n",u);
	for(int i=0;i<T[u].size();i++)
	{
		int v=T[u][i];
		if(v==f) continue;
		dfs2(v,u);
	}
	if(u==rt) return ;
	if(d[u]&1) ans[++cnt].u=u,ans[cnt].v=f,d[u]++;
	else ans[++cnt].u=f,ans[cnt].v=u,d[f]++;
	//printf("%d %d %d %d\n",u,d[u],ans[cnt].u,ans[cnt].v);
}
void Init()
{
	for(int i=1;i<=n;i++)
		ft[i]=i;
	int tot=0;
	for(int i=1;i<=m;i++)
	{
		if(Union(edge[i].u,edge[i].v))
		{
			T[edge[i].u].push_back(edge[i].v);
			T[edge[i].v].push_back(edge[i].u);
			if(rt==-1) rt=edge[i].u;
			vis[i]=1;
			tot++;
		}
		if(tot==n-1) break;
	}
	cnt=0;
	for(int i=1;i<=m;i++)
		if(!vis[i])
		{
			ans[++cnt].u=edge[i].u,ans[cnt].v=edge[i].v;
			d[edge[i].u]++;
			//printf("**%d %d\n",edge[i].u,edge[i].v);
		}
	dfs2(rt,-1);
}
int main()
{
	//freopen("degree.in","r",stdin);
	//freopen("degree.out","w",stdout);
	scanf("%d %d",&n,&m);
	if(m&1)
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<=m;i++)
	{
		int u,v;scanf("%d %d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(v);
		edge[++cnt].u=u,edge[cnt].v=v;
	}
	//dfs(1);//Find ST
	Init();//Find ST
	for(int i=1;i<=cnt;i++)
		printf("%d %d\n",ans[i].u,ans[i].v);
	return 0;
}

Measured memory_bytes: 20992
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

#define ul unsigned long long

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

	if (N>2 && M>2) cout << (N-2)*(M-2) << endl;
	else if (N==1 && M==1) cout << 1 << endl;
	else if (N==1) cout << (M-2) << endl;
	else if (M==1) cout << (N-2) << endl;
	else cout << 0 << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>

#define INF_LL 9000000000000000000
#define INF 2000000000

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

using namespace std;

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

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(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(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

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

/*
int main(void){
	int n, k;
	int a[100000];
	int sum_k[100000];
	cin >> n >> k;

	memset(sum_k, 0, sizeof(sum_k));
	REP(i, n){
		cin >> a[i];
		for(int j = max(0, i-k+1);j <= i;j++){
			sum_k[j] += a[i];
		}
	}
}
*/

int main(void){
	int a[7];
	ll res = 0;
	ll res2 = 0;
	REP(i, 7){
		cin >> a[i];
	}
	res = a[1]*2;
	res2 = res;
	res += a[0]/2*4;
	res += a[3]/2*4;
	res += a[4]/2*4;
	res += min(a[0]%2, min(a[3]%2, a[4]%2))*6;
	res = res /2;
	if(a[0] && a[3] && a[4]){
		res2 += 6;
		a[0]--;
		a[3]--;
		a[4]--;
	}
	res2 += a[0]/2*4;
	res2 += a[3]/2*4;
	res2 += a[4]/2*4;
	cout << max(res, res2/2) << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int N,count=0;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  for(int i=0;i<N;++i) cin >> A.at(i);
  for(int j=0;j<N;++j) cin >> B.at(j);
  for(int k=0;k<N;++k){
    if(A.at(k)>B.at(k)) count+=A.at(k)-B.at(k);
  }
  cout << count << endl;
}

Measured memory_bytes: 256
class Dice
	attr_reader :top

  def initialize(ary)
    @top, @front, @right, @left, @back, @bottom = ary
  end

  def roll(way)
    case way.downcase
    when 'e'
      tmp = @top
      @top = @left
			@left = @bottom
			@bottom = @right
			@right = tmp
    when 'w'
			tmp = @top
			@top = @right
			@right = @bottom
			@bottom = @left
			@left = tmp
    when 's'
			tmp = @top
			@top = @back
			@back = @bottom
			@bottom = @front
			@front = tmp
    when 'n'
			tmp = @top
			@top = @front
			@front = @bottom
			@bottom = @back
			@back = tmp
    end
  end
end

dice = Dice.new(gets.chomp.split(/\s/).map(&:to_i))
order = gets.chomp.split('')
order.each{ |way| dice.roll(way) }
puts dice.top

Measured memory_bytes: 8688
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;


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; }

int main(){

    long long N;
    vector <long long> arr; 

    cin >> N;
    for(int i=0; i < N; ++i){
        long long tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    long long sum = 0;
    long long max = arr[0];
    for(int i=1; i < N; ++i){
        if(max>arr[i]){
            sum += (max-arr[i]);
        }
        else{
            max = arr[i];
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 5296
//Author - Rahil Malhotra
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int32_t main()
{
    IOS;
    int n;
    cin>>n;
    int arr[2*n+10]={};
    int sum[2*n+10]={};
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        if(i%2)
            sum[i]=sum[i-1]+arr[i];
        else
            sum[i]=sum[i-1]-arr[i];
    }
    cout<<sum[n];
    for(int i=n+1;i<2*n;i++)
    {
        cout<<" ";
        arr[i]=arr[i-n];
        if(i%2)
            sum[i]=sum[i-1]+arr[i];
        else
            sum[i]=sum[i-1]-arr[i];
        if(i%2)
            cout<<(sum[i]-sum[i-n]);
        else
            cout<<(-sum[i]+sum[i-n]);
    }
}


Measured memory_bytes: 6744
import java.util.*;

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

        Scanner sc = new Scanner(System.in);
        
        double N = sc.nextInt();
        double K = sc.nextInt();
        double ans = K * Math.pow(K-1,N-1);
        
        System.out.println((int)ans);
    }
}


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

#define ll long long
#define mod 1000000007
#define pll pair<long long,long long>
#define pdd pair<long double,long double>
#define vll vector<ll>
#define rep(i,j,n) for(int i=j;i<n;i++)
#define mp make_pair
#define pb push_back
#define pf push_front
#define inf 1e17
priority_queue<pll,vector<pll>,greater<pll> >pq;
priority_queue<ll,vector<ll>,greater<ll> >pq1;

ll result(ll a, ll b, ll p){
    ll ans=1;
    if(b==(-1))
        b=p-2;
    while(b){
        if(b&1){
            ans=(ans*a)%p;
        }
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

int main(){
    if(fopen("input.txt", "r"))
    freopen("input.txt", "r", stdin),
    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    cin >> s;
    if(s=="AAA" || s=="BBB")
        cout<<"No\n";
    else
        cout<<"Yes\n";


    return 0;
        
}


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

int main(){
  int n,k,a;
  cin >>n>>k;
  
  a = 1;
  
  for (int i = 0; i<n ; i++){
    if (a + k <= a * 2){
      a += k;
    }
    else{
      a += a;
    }
  }
  cout << a<<endl;
}

Measured memory_bytes: 256
import numpy as np
import sys
input=sys.stdin.readline

n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=np.zeros(W+1,dtype="i8")
for w,v in wv:
    np.maximum(dp[w:],dp[:W+1-w]+v,out=dp[w:])
print(dp[-1])


Measured memory_bytes: 14624
A = int(input())
B = int(input())
C = int(input())
X = int(input())


res = 0
for i in range(A+1):
    for j in range(B+1):
        for k in  range(C+1):
            if i*500+100*j+50*k == X:
                res += 1
print(res)

Measured memory_bytes: 39536
#include <bits/stdc++.h>
using namespace std;
#define fo(i,n) for(int i = 0; i < n; i++)
#define pb push_back
#define all(c) c.begin(),c.end()



int main()
{
    double r;
    cin >> r;
    cout << 2.0*r*3.1415926535 << endl;


}



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

int main()
{
  int n,d;
  cin >> n >> d;
  
  int x[n][d];
  for(int i = 0; i < n; i++){
    for(int j = 0; j < d; j++){
      cin >> x[i][j];
    }
  }
  
  long double sum = 0;
  int ans = 0;
  for(int i = 0; i < n; i++){
    for(int j = i+1; j < n; j++){
      for(int k = 0; k < d; k++){
        sum += (long double)(abs(x[i][k] - x[j][k]) * abs(x[i][k] - x[j][k]));
      }//for
      sum = sqrt(sum);
      if(floor(sum) == ceil(sum)){
         ans++;
      }//if
      sum = 0;
    }//for
   
  }//for
  
  cout << ans << endl;
}

Measured memory_bytes: 3636
N=int(input())
li=list(map(int,input().split()))

counter=0

for i in range(N):
    if li[i]<0:
        counter=counter+1

li2=li

for i in range(N):
    li2[i]=abs(li[i])

if counter % 2==0:
    mi=0

if counter % 2!=0:
    mi=min(li2)

sumli=0
for i in range(N):
    sumli=abs(li[i])+sumli

sumli=sumli -(mi*2)

print(sumli)

Measured memory_bytes: 14284
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

void solve(long long N, std::vector<long long> a)
{
    ll tmp = 0;
    for (int i = 0; i < N; i++)
    {
        if (tmp + 1 == a[i])
        {
            tmp++;
        }
    }
    if (tmp == 0)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << N - tmp << endl;
    }
}

int main()
{
    long long N;
    scanf("%lld", &N);
    std::vector<long long> a(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &a[i]);
    }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
int main()
{
  int n;
  string a;
  cin >>n >> a;
  int ans =0;
  REP(i,n - 2){
    if(a[i] =='A'){
      if(a[i + 1] == 'B'&&a[i + 2] == 'C'){
	ans ++;
      }
    }
  }
  cout <<ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>iP;
typedef pair<P,P>PP;
#define F first
#define S second

int dp[1<<8],n,m,h,k,s,t,p,l,d,I[5],dis[111][25];
vector<PP>v[111];

void input(){
  r(i,(1<<8))dp[i]=1e9;
  r(i,111)v[i].clear();
  cin>>n>>m>>h>>k;
  if(!n)exit(0);
  r(i,m){
    r(j,5)cin>>I[j]; I[0]--; I[1]--; I[4]--;
    v[I[0]].push_back(PP(P(I[1],I[2]),P(I[3],I[4])));
    v[I[1]].push_back(PP(P(I[0],I[2]),P(I[3],I[4])));
  }
  cin>>s>>t>>p; s--; t--;
  dp[0]=0;
  r(i,p){
    int sum=0,x;
    cin>>l>>d;
    r(j,l){
      cin>>x; x--;
      sum|=(1<<x);
    }
    r(j,(1<<k)) if(dp)dp[j|sum]=min(dp[j|sum],dp[j]+d);
  }
}

int dij(int x){
  int ans=1e9;
  r(i,111)r(j,25)dis[i][j]=1e9;
  priority_queue<iP,vector<iP>,greater<iP> >q;
  dis[s][0]=0;
  q.push(iP(0,P(s,0)));
  while(!q.empty()){
    iP p=q.top();q.pop();
    int cost=p.F;
    int now=p.S.F;
    int H=p.S.S;
    if(dis[now][H]<cost)continue;
    r(i,v[now].size()){
      PP pp=v[now][i];
      int nex=pp.F.F;
      int ncos=pp.F.S;
      int nh=pp.S.F;
      int kai=pp.S.S;
      if((1<<kai)&x)ncos=cost;
      else ncos+=cost;
      if(nh+H>h)continue;
      if(dis[nex][nh+H]>ncos){
        dis[nex][nh+H]=ncos;
        q.push(iP(ncos,P(nex,nh+H)));
      }
    }
  }
  r(i,25)ans=min(ans,dis[t][i]);
  return ans+dp[x];
}

signed main(){
  while(1){
    int ans=1e9;
    input();
    r(i,(1<<k))ans=min(ans,dij(i));
    cout<<(ans==1e9?-1:ans)<<endl;
  }
}


Measured memory_bytes: 3252
#!/usr/bin/env python
# coding: utf-8

# In[3]:


#import sys
S = input()


# In[4]:


for i, s in enumerate(S):
    if ((i+1)%2 == 1 and s == 'L') or ((i+1)%2 == 0 and s == 'R'):
        print('No')
        break
else:
    print('Yes')


# In[ ]:






Measured memory_bytes: 2940
x,n=map(int, input().split())
p=list(map(int, input().split()))

if p == []:
    print(x)
    exit()

if x not in p:
    print(x)
    exit()

tmp1 = x
tmp2 = x

for i in range(1,500):
    tmp1 = tmp1 - 1
    tmp2 = tmp2 + 1
    if tmp1 not in p:
        print(tmp1)
        exit()
    if tmp2 not in p: 
        print(tmp2)
        exit()


Measured memory_bytes: 9196
#include "bits/stdc++.h"

using namespace std;

//typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)


signed main(){

	int N, W;
	int w[101], v[101];

	cin >> N >> W;
	for (int i = 0; i<N; i++)
		cin >> w[i] >> v[i];

	int dp[101][100001] = { 0 };

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

	return 0;
}


Measured memory_bytes: 79104
#include <stdio.h>
#include <iostream>

using namespace std;

int convert(char c)
{
  switch (c)
  {
  case 'A':
    return 10;
  case 'B':
    return 11;
  case 'C':
    return 12;
  case 'D':
    return 13;
  case 'E':
    return 14;
  case 'F':
    return 15;
  default:
    throw new exception();
  }
}

int main()
{
  char x, y;
  cin >> x >> y;
  int xn = convert(x);
  int yn = convert(y);
  if (xn < yn)
  {
    cout << '<' << endl;
  }
  else if (yn < xn)
  {
    cout << '>' << endl;
  }
  else
  {
    cout << '=' << endl;
  }
}


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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  int res = n * (n - 1) / 2 + m * (m - 1) / 2;
  cout << res << '\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
 
using namespace std;
int sv[16];

signed main(){
	int n;
	long long a = 0;
	char rp;
	bool br = 0;
	int dg;
	dg = 0;
	for(int i = 10; i >= 1; i--){
		cout << "? " << (int)pow(10, i) - 1 << "\n";
		fflush(stdout);
		cin >> rp;
		if(rp == 'N'){
			dg = i + 1;
			break;
		}
	}
	if(dg == 0){
		for(int i = 10; i >= 0; i--){
			cout << "? " << (int)pow(10, i) << "\n";
			fflush(stdout);
			cin >> rp;
			if(rp == 'Y' && i == 10){
				cout << "! 1\n";
				exit(0);
			}
			if(rp == 'Y'){
				dg = i + 1;
				break;
			}
		}
	}
	for(int i = 1; i < dg; i++){
		int l = 0, r = 9;
		a = a * 10;
		while(l != r){
			int mid = (l + r + 1) / 2;
			cout << "? " << a + mid << "\n";
			fflush(stdout);
			cin >> rp;
			if(rp == 'Y'){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		a += l;
	}
	a = a * 10;
	if(a == 0) a = 1;
	for(int i = 0; i <= 9; i++){
		cout << "? " << (a + i) * 10 << "\n";
		fflush(stdout);
		cin >> rp;
		if(rp == 'Y'){
			a = a + i;
			break;
		}
	}
	cout << "! " << a << "\n";
	fflush(stdout);
	exit(0);
	
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  Int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){}
  
  void init(Int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  inline T reflect(Int k){
    return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }
  inline void eval(Int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void thrust(Int k){
    for(Int i=height;i;i--) eval(k>>i);
  }
  inline void recalc(Int k){    
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }
  void update(Int a,Int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(Int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(Int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }
  T query(Int a,Int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(Int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> l(m),r(m),a(m);
  for(Int i=0;i<m;i++) cin>>l[i]>>r[i]>>a[i];

  vector<vector<Int> > idx(n+1);
  for(Int i=0;i<m;i++) idx[r[i]].emplace_back(i);

  Int sum=0;
  for(Int i=0;i<m;i++) sum+=a[i];

  auto f=[](Int a,Int b){return min(a,b);};
  auto g=[](Int a,Int b){return a+b;};
  const Int INF = 1e15;
  SegmentTree<Int, Int> seg(f,g,g,INF,0);
  seg.build(vector<Int>(n+1,INF));
  seg.set_val(0,0);
  
  for(Int i=1;i<=n;i++){
    Int val=seg.query(0,i);
    seg.set_val(i,val);
    for(Int k:idx[i])
      seg.update(0,l[k],a[k]);
  }
  cout<<sum-seg.query(0,n+1)<<endl;
  return 0;
}


Measured memory_bytes: 25600
h, w = input().split()
h = int(h)
w = int(w)
lines = list()
c = [0]*w
for _ in range(h):
    line = input()
    if line=="."*w:
        continue
    lines.append(line)
    for i in range(w):
        if line[i]==".":
            c[i] += 1
h = len(lines)
ans = list()
for j in range(h):
    line = ""
    for i in range(w):
        if c[i] != h:
            line += lines[j][i]
    ans.append(line)
print("\n".join(ans))

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

class DT
{
	public:
	int i,p;

	DT(int n){i=n;p=0;}

	bool operator<(const DT &a) const
	{
		return (p!=a.p?p>a.p:i<a.i);
	}
};

int main()
{
	int N,M,X;
	while(cin >> N >> M, (N||M))
	{
		vector<DT> v;
		for(int m=0; m<M; m++)
		{
			v.push_back(DT(m+1));
		}

		for(int n=0; n<N; n++)
		{
			for(int m=0; m<M; m++)
			{
				cin >> X;
				v[m].p += X;
			}
		}

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

		for(int m=0; m<M-1; m++)
		{
			cout << v[m].i << " ";
		}
		cout << v[M-1].i << endl;
	}
	return 0;
}

Measured memory_bytes: 908
#AGC033-A Darker and Darker
"""
愚直にbfs(queueが無くなるまで)
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#迷路plane
H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

def bfs(lst):
    deq = deque(lst)
    ans = 0
    while deq:
        h,w,now = deq.popleft()
        for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not (0 <= h+a < H and 0 <= w+b < W):continue
            if maze[h+a][w+b]=="#":continue
            else:
                maze[h+a][w+b] = "#"
                ans = max(ans,now+1)
                deq.append([h+a,w+b,now+1])
    return ans

lst1 = []
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            lst1.append([i,j,0])

print(bfs(lst1))

Measured memory_bytes: 180236
//#include<bits/stdc++.h>	// 全てのヘッダーファイルをinclude
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR (i,n) for(int i=n;i>0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define MOD 1e9+7	// int 1000000007
const int inf{int(1e9)};	// inf = 1000000000 // 1e9 はdouble型
using namespace std;
typedef long long ll;


int main(void) {
	string o, e;
	cin >> o >> e;
	int l = o.length() + e.length();
	if (l % 2 == 0) {
		REP(i, l/2) cout << o[i] << e[i] << flush;
	}
	else {
		REP(i, l / 2) cout << o[i] << e[i] << flush;
		cout << o[l / 2] << flush;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main(){
	double a[200],sum;
	sum = 0;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	for (int i = 0; i < n; i++){
		sum += 1 / a[i];
	}
	sum = 1 / sum;
	printf("%10lf\n", sum);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

vector<ll>a;

int main() {
	ll n;
	cin>>n;
	for(int i=0;i<n;i++){
		ll x;
		cin>>x;
		a.push_back(x);
	}
	sort(a.begin(),a.end());
	ll l=a[n-1];		
	ll midu=l;
	ll r1;
	ll ch=INF;
	for(int i=0;i<n-1;i++){
		ll now=a[i];
		now*=2;
		now=abs(now-midu);
		if(now<ch){
			ch=now;
			r1=a[i];
		}

	}
  cout << l<<" "<<r1;
  return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long 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;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b>>1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;


//////////////////////////
vector<mint> frac, ifrac;
void finit(ll X) {
	frac.assign(X + 1, 1);
	ifrac.assign(X + 1, 1);

	repn(i, X) {
		frac[i] = frac[i - 1] * i;
		ifrac[i] = ifrac[i - 1] / i;
	}

}

mint com(ll n, ll m) {
	if (n < 0 || m < 0 || n < m) { return 0; }
	return frac[n] * ifrac[m] * ifrac[n - m];
}

int main() {
	ll A, B;
	cin >> A >> B;

	mint ans = 0;
	finit(A+B);

	repn(x, B + 1) {
		repn(y, B - x) {
			mint now = com(B-1, x-1) * com(B - x-1, y-1) * com(A-(B-x)-(B-x-y)+2, 2);
			ans += now;
			//cout << x << " " << y << " " << now << endl;
		}

		if (x == B) {
			ans += A + 1;
		}
	}

	cout << ans << endl;
	
}


Measured memory_bytes: 256