akhauriyash/Code-Regression huggingface dataset:
loop do
  a = gets.split.map(&:to_i)
  break if a[0]==0
  c=0
  a.map!{|x| x>9 ? 10 : x}
  sum = a.inject(0){|x,y|
    if y==1
      c=1
    end
    x+y}
  if sum<12 && c!=0
    sum+=10
  end
  sum = 0 if sum>21
  puts sum
end

Measured memory_bytes: 2480
n, k =map(int, input().split())
STR = input()
str = STR.lower()

if k == 1:
  sTR = str[0] + STR[1:]
elif k == n:
  sTR = STR[:n-1] + str[n-1]
else:
  sTR = STR[:k-1] + str[k-1] + STR[k:]

print(sTR)


Measured memory_bytes: 2940
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<set>
#include<algorithm>
#define ll long long
#define rg register
#define go(i,x,a) for(rg int i=a;i<x;i++)
using namespace std;

ll n;

inline ll rd(){
	ll ret=0,af=1; char gc=getchar();
	while(gc < '0' || gc > '9'){ if(gc == '-') af=-af; gc=getchar(); }
	while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar();
	return ret*af;
}

int main(){
	n=rd(); ll ss=0;
	for(rg ll i=1;i*(i+2) <= n;i++){
		ll j=n/i;
		if(i*j != n) continue;
		ss+=j-1;
	}
	printf("%lld",ss);
	return 0;
}

Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <climits>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>

using namespace std;

const int MAX_N = 100000;

int N, T;
int A[MAX_N];
unordered_map<int, int> mp;

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

    cin >> N >> T;

    int minc = INT_MAX;
    int maxb = 0;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        minc = min(minc, A[i]);
        int bft = A[i] - minc;
        maxb = max(maxb, bft);
        if (mp.count(bft)) {
            mp[bft]++;
        } else {
            mp.insert(make_pair(bft, 1));
        }
    }

    cout << mp[maxb] << "\n";

    return 0;
}

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

int main() {
	string s;
	cin >> s;
	int n = stoi(s);
	int sn = 0;
	for (int i = 0; i < s.size(); ++i) {
		string sub = s.substr(i,1);
		sn += stoi(sub);
	}
	string out;
	if (n % sn == 0) {out = "Yes";} else {out = "No";}
	
	cout << out << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>

int main()
{
    int n;
    cin>>n;
    int maxi=n+1,ans=0;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        maxi=min(a,maxi);
        if(a==maxi)
            ans++;
    }
    cout<<ans;
}

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

using namespace std;

#define MAX 3002

#define MOD 1000000007

int n;
int m;

long long int dp[MAX][MAX];

deque<pair<int, int> > v;

char buf[MAX];

vector<int> V;

int im[MAX];

int rng(int a, int b){
	if (a > b)return 0;
	int r = im[b];
	if (a){
		r -= im[a - 1];
	}
	return max(r,0);
}


int belong[MAX];
int att[MAX];

int add_point[MAX];

int main(){
	scanf("%d%d", &n, &m);
	scanf("%s", buf);
	for (int i = 0; i < n; i++){
		V.push_back(buf[i] - '0');
		if (V.back() == 1){
			im[i]++;
		}
		if (i){
			im[i] += im[i - 1];
		}
	}
	memset(att, -1, sizeof(att));
	memset(add_point, -1, sizeof(add_point));
	int pr_l = -1;
	int pr_r = -1;
	for (int i = 0; i < m; i++){
		int l, r;
		scanf("%d%d", &l, &r);
		l--;
		r--;
		if (pr_r >= r){
			continue;
		}
		if (pr_l < l){
			v.push_back(make_pair(l, r));
		}
		else{
			v.back().second = max(v.back().second, r);
		}
		pr_l = l;
		pr_r = r;
		belong[l]++;
		belong[r + 1]--;
		att[l] = v.size()-1;
		add_point[l] = v.size()-1;
	}

	for (int i = 0; i < n; i++){
		if (i){
			belong[i] += belong[i - 1];
		}
		if (belong[i]&&att[i] == -1){
			att[i] = att[i - 1];
		}
		if (belong[i] == 0){
			att[i] = -1;
		}
	}
	if (v[0].first == 0){
		dp[0][rng(v[0].first, v[0].second)]=1;
	}
	else{
		dp[0][V[0]] = 1;
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < MAX; j++){
			if (dp[i][j]){
				int all = 1;
				if (belong[i]){
					all = v[att[i]].second - v[att[i]].first + 1;
					all -= i - v[att[i]].first;
				}
				int cnt0 = all - j;
				int cnt1 = j;
				int add_j = 0;
				if (add_point[i+1] != -1){
					int cur_ed = i + all - 1;
					int nex_ed = v[add_point[i + 1]].second;
					add_j += rng(cur_ed+1, nex_ed);
				}
				else{
					if (belong[i] == 0){
						add_j += rng(i + 1, i + 1);
					}
					else{
						if (all == 1){
							add_j += rng(i + 1, i + 1);
						}
					}
				}
				if (cnt0){
					int nex_j = j+add_j;
					dp[i + 1][nex_j] += dp[i][j];
					if (dp[i + 1][nex_j] >= MOD){
						dp[i + 1][nex_j] %= MOD;
					}
				}
				if (cnt1){
					int nex_j = j - 1+add_j;
					dp[i + 1][nex_j] += dp[i][j];
					if (dp[i + 1][nex_j] >= MOD){
						dp[i + 1][nex_j] %= MOD;
					}
				}
			}
		}
	}
	int ans = dp[n][0];
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 12800
from fractions import gcd

def lcm(a, b):
    return (a*b)//gcd(a,b)

a, b, c, d = map(int, input().split())

print(b - b//c - b//d + b//lcm(c, d) - (a-1 - (a-1)//c - (a-1)//d + (a-1)//lcm(c, d)))


Measured memory_bytes: 5048
#include <stdio.h>
int a[200001];
int b[200001];

long long nc2(int n) {
  return (long long)n * (long long)(n - 1) / 2;
}

int main() {
  int n;
  scanf("%d", &n);

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

  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += nc2(b[i]);
  }

  for (int i = 0; i < n; i++) {
    printf("%lld\n", sum - (b[a[i]]-1));
  }
  return 0;
}

Measured memory_bytes: 3584
n, m  = gets.strip.split.map(&:to_i)
as = gets.strip.split.map(&:to_i)

cs = [2,5,5,4,5,6,3,7,6].map.with_index {|cost, num| [cost, num+1] }.select {|_, num| as.include?(num) }.to_h

dp = Array(n+1)

(n+1).times do |i|
  tmp = cs[i].to_i.to_s
  cs.each do|cost, num|
    next if i-cost<0 || dp[i-cost].to_i.zero?

    c = dp[i-cost] > num.to_s ? dp[i-cost]+num.to_s : num.to_s+dp[i-cost]
    tmp = c if c.length > tmp.length || c.length==tmp.length && c>tmp
  end
  dp[i]=tmp
end

puts dp[n]

Measured memory_bytes: 48892
import java.util.Scanner;

class Main{


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		String AA = sc.next();
		String BB = sc.next();
		String CC = sc.next();
		
		
		StringBuilder A = new StringBuilder(AA);
		StringBuilder B = new StringBuilder(BB);
		StringBuilder C = new StringBuilder(CC);

		
		String player = "A";
		while(true){
			//System.out.println(player);
			
			if(player == "A"){
				if(A.length() == 0){
					System.out.println("A");
					return;
				}
				
				if(A.charAt(0) == 'a'){
					player = "A";
					A = A.deleteCharAt(0);
				}else if(A.charAt(0) == 'b'){
					player = "B";
					A = A.deleteCharAt(0);
				}else if(A.charAt(0) == 'c'){
					player = "C";
					A = A.deleteCharAt(0);
				}
				
			}else if(player == "B"){
				if(B.length() == 0){
					System.out.println("B");
					return;
				}
				
				if(B.charAt(0) == 'a'){
					player = "A";
					B = B.deleteCharAt(0);
				}else if(B.charAt(0) == 'b'){
					player = "B";
					B = B.deleteCharAt(0);
				}else if(B.charAt(0) == 'c'){
					player = "C";
					B = B.deleteCharAt(0);
				}
				
				
			}else if(player == "C"){
				if(C.length() == 0){
					System.out.println("C");
					return;
				}
				
				if(C.charAt(0) == 'a'){
					player = "A";
					C = C.deleteCharAt(0);
				}else if(C.charAt(0) == 'b'){
					player = "B";
					C = C.deleteCharAt(0);
				}else if(C.charAt(0) == 'c'){
					player = "C";
					C = C.deleteCharAt(0);
				}
				
				
			}
			
		}
		
	}
}

Measured memory_bytes: 23764
import sys
S=input()
N=len(S)
#L=['B','D','E','F','G','H','I','J','K','L','N','M','O','P','Q','R','S','T','U','V','W','X','Y','Z']
if S[0]!='A':
    print('WA')
    sys.exit()
ans=0
for i in range(2,N-1) :
    if S[i]=='C':
        ans+=1
if ans!=1:
    print('WA')
    sys.exit()
for i in range(N) :
    if S[i] in 'AC':
        continue
    if S[i].isupper():
        print('WA')
        sys.exit()
print('AC')

Measured memory_bytes: 38384
let n = read_int ()

let a = Array.init n (fun _ -> Scanf.scanf "%d\n" (fun x -> x))

let () =
  let rec f count value i =
    if i = n then -1
    else
      let next = a.(value) in
      if next = 2 then count + 1
      else f (count + 1) (next - 1) (i + 1)
  in
  f 0 0 0 |> Printf.printf "%d\n"

Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(ll i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll n,m,ans=0;
void Main(){
    cin>>n;
    string S;cin>>S;
    For(i,0,S.size()){
        S.at(i)=((S.at(i)-'A')+n)%26+'A';
    }
    cout<<S<<endl;
}
int main(){
    Main();
    return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;

int main() {
	int N, M;
	while (cin >> N >> M, N) {
		vi field(N);
		REP(i, N) {
			cin >> field[i];
		}
		vi dice(M);
		REP(i, M) {
			cin >> dice[i];
		}

		int pos = 0;
		REP(i, M) {
			pos += dice[i];
			if (pos >= N - 1) { 
				cout << i + 1 << endl;
				break;
			}

			pos += field[pos];
			if (pos >= N - 1) {
				cout << i + 1 << endl;
				break;
			}
			if (pos < 0) {
				pos = 0;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define PP pair<int,int> // x, w
#define P pair<PP,int> // , id
//#define DEBUG
int main(){
  int W,w,q;
  char c;
  int id;
  vector<P> v;

  while( cin>>W>>q && (W|q) ){
    v.clear();
    for( int lp=0;lp<q;lp++ ){
      cin >> c;
      switch(c){
      case 's':
	{
	  cin >> id >> w;
	  int x=-1, bg,en;
	  if( v.empty() ){
	    if( w <= W )
	      x=0;
	  }else{
	    bg=0; en=v[0].first.first;
	    if( bg + w <= en )   x=bg;
	  }
	  for( int i=1;x<0 && i<(int)v.size();i++ ){
	    bg=v[i-1].first.first + v[i-1].first.second;
	    en=v[i].first.first;
	    if( bg + w <= en )   x=bg;
	  }
	  if( x<0 ){
	    bg=v[v.size()-1].first.first + v[v.size()-1].first.second;
	    en=W;
	    if( bg + w <= en )   x=bg;
	  }
	  if( x>=0 ){
	    cout << x << endl;
	    v.push_back( P( PP(x,w), id) );
	    sort( v.begin(), v.end() );
	  }else
	    cout << "impossible" << endl;

#ifdef DEBUG
	  for( int i=0;i<(int)v.size();i++ ){
	    PP p=v[i].first;
	    id = v[i].second;
	    cout << "  " << id << " : " << p.first << " " << p.second << endl;
	  }
#endif
	  break;
	}
      case 'w':
	{
	  cin >> id;
	  for( int i=0;i<(int)v.size();i++ ){
	    if( v[i].second == id ){
	      v.erase( v.begin()+i );
	      sort( v.begin(), v.end() );
	      break;
	    }
	  }
	}
	break;
      }
    }
    cout << "END" << endl;
  }

  return 0;
}

Measured memory_bytes: 1196
x = gets.chomp.split(" ").map(&:to_i)
on = Array.new()
(x.max).times{|i| on[i] = on[i].to_i + 0}
for i in x[0]..x[1] do
  on[i] = on[i].to_i + 1
end
for i in x[2]..x[3] do
  on[i] = on[i].to_i + 1
end
if on.count(2) == 0 then
  puts 0
else
  puts on.count(2)-1
end

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

int main(){
	int a,b,k;
	cin >> a >> b >> k;
	for(int i = a; i < a + k; i++){
		if(i <= b)cout << i << endl;
	}
	for(int i = b - k + 1; i <= b; i++){
		if(i >= a + k) cout << i << endl;
	}
}

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

char str[200010];

int main(void){

    scanf("%s",str);
    int len = strlen(str);

    int bcnt = 0;
    int wcnt = 0;

    for(int i=0;i<len;i++){
        if(str[i] == 'B'){
            bcnt++;
        }else{
            wcnt++;
        }
    }

    if(!bcnt || !wcnt){
        printf("0");
        return 0;
    }

    ll ans = 0;
    for(int i=0;i<len;i++){
        if(str[i] == 'W') ans += i;
    }
    for(int i=0;i<wcnt;i++){
        ans -= i;
    }

    cout << ans;

    return 0;
}


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

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

  int n, m; cin >> n >> m;
  if(n >= m) {
    cout << 0 << '\n';
    return 0;
  }
  vector<int> x(m);
  rep(i, m) cin >> x[i];
  sort(x.begin(), x.end());

  vector<int> dif(m-1);
  rep(i, m-1) dif[i] = x[i+1] - x[i];
  sort(dif.begin(), dif.end(), greater<int>());

  int ans = x[m-1]-x[0];
  rep(i, n-1) ans -= dif[i];

  cout << ans << '\n';
  return 0;
}


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

int main() {
    string s;
    cin >> s;
    string target = "keyence";
    for (int p = 0; p <= 7; p++) {
        string t;
        for (int i = 0; i < p; i++) {
            t += s.at(i);
        }
        for (int i = (int)s.size() - (7 - p); i < (int)s.size(); i++) {
            t += s.at(i);
        }
        
        if (t == target) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
//46
#include<iostream>
#include<complex>

using namespace std;

int main(){
  complex<double> p[1000];
  p[0]=complex<double>(1,1);
  for(int i=1;i<1000;i++){
    p[i]=p[i-1]-p[i-1]*complex<double>(0,-1)/abs(p[i-1]);
  }
  for(int n;cin>>n,n!=-1;){
    cout<<p[n-2].real()<<endl<<p[n-2].imag()<<endl;
  }
  return 0;
}
    

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
int main(void){
   string A,B,C;
   cin>>A>>B>>C;
   
   cout<<A[0]<<B[1]<<C[2]<<endl;
   
   
  
}

Measured memory_bytes: 3596
#!/usr/bin/env python3


def compute(s):
    board = [c == "W" for c in s]
    n = len(board)
    ans = 0
    for i in range(1, n):
        if board[i] != board[i - 1]:
            ans += 1
    return ans


def main():
    print(compute(input()))


if __name__ == '__main__':
    main()


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

const int N = 100400;

int n;
pair<int,int> p[N];

int main() {
    cin>>n;
    for(int i=0;i<n;i++) {
        int l,x;
        cin>>l>>x;
        p[i] = make_pair(l+x,l-x);
    }
    sort(p,p+n);
    int ans = 0, t = -1000000009;
    for(int i=0;i<n;i++) {
        if(t <= p[i].second) {
            ans++;
            t = p[i].first;
        }
    }
    cout<<ans<<endl;
    return 0;
}




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

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int h, w; cin >> h >> w;
  string s[h];
  for (int i = 0; i < h; i++) cin >> s[i];
  int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
  bool b = 1;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (s[i][j] == '#') {
        bool t = 0;
        for (int k = 0; k < 4; k++) {
          int x = i + dx[k], y = j + dy[k];
          if (x >= 0 and x < h and y >= 0 and y < w) {
            if (s[x][y] == '#') t = 1;
          }
        }
        if (t == 0) {
          cout << "No" << "\n";
          return 0;
        }
      }
    }
  }
  cout << "Yes" << "\n";
  return 0;
}

Measured memory_bytes: 256
//BROWNIE TK

#include <bits/stdc++.h>
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front()
#define si size()
#define be begin()
#define en end()
#define all(v) v.be, v.en
#define le length()
#define mp make_pair
#define mt make_tuple
#define F first
#define S second

#define forz(i, n) for (int i = 0; i < n; i++)
#define forzm(i, m, n) for (int i = m; i < n; i++)
#define rforz(i, n) for (int i = n - 1; i >= 0; i--)
#define rforzm(i, m, n) for (int i = n - 1; i >= m; i--)
#define deci(n) fixed << setprecision(n)
#define high(n) __builtin_popcount(n)
#define parity(n) __builtin_parity(n)
#define ctz(n) __builtin_ctz(n)
#define lb lower_bound
#define ub upper_bound
#define er equal_range
#define maxe *max_element
#define mine *min_element
#define mod 1000000007
#define mod2 998244353
#define kira ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl

#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetlli tree<lli, null_type, less<lli>, rb_tree_tag, tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
#define ofk order_of_key
#define fbo find_by_order
using namespace std;

/*STD fucntions*/
lli power(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        //y must be even now
        y = y >> 1; //y=y/2
        x = (x * x) % p;
    }
    return res;
}
lli gcd(lli a, lli b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
lli lcm(lli a, lli b)
{
    return a * b / gcd(a, b);
}
lli modi(lli a, lli m)
{
    // fermat little thm where m is prime
    return power(a, m - 2, m);
}
/*CODE BEGINS*/

int main()
{
    kira;
    lli a,b;
    cin>>a>>b;
    lli g=__gcd(a,b);
    lli c=1;
    if(g%2==0)c++;
    while(g%2==0)
    {
        g=g/2;
    }
    for(int i=3;i<=sqrt(g);i+=2)
    {
        if(g%i==0)c++;
        while(g%i==0){g=g/i;}
    }
    if(g>2)
    {
        c++;
    }
    p1(c);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'
#define N 100001
#define mod 1e9+7
using namespace std;
typedef long long ll;
const ll INF = (ll)1e18 ;
ll dp[101][N];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,w;
	cin>>n>>w;
	ll wt[n],val[n];
	for(ll i=0;i<n;i++){
	    cin>>wt[i]>>val[i];
	}
	for(ll i=0;i<n+1;i++){
	    for(ll j=0;j<N;j++){
	        dp[i][j]=INF;
	    }
	}
	for(ll i=0;i<n+1;i++)dp[i][0]=0;
	for(ll i=1;i<n+1;i++){
	    //dp[0][0]=0;
	    for(ll j=1;j<N;j++){
	        if(j>=val[i-1]){
	        dp[i][j]=min(dp[i-1][j],wt[i-1]+dp[i-1][j-val[i-1]]);
	        }else{
	            dp[i][j]=dp[i-1][j];
	        }
	       
	    }
	}
	ll res=0;
	for(ll i=0;i<n+1;i++){
	    for(ll j=1;j<N;j++){
	        if(dp[i][j]<=w){
	            res=max(res,j);
	        }
	    }
	}
	cout<<res;
	return 0;
}


Measured memory_bytes: 82556
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
inline int add(int a,int b)
{
	if((a+=b)>=mod)a-=mod;
	return a;
}
inline int mult(int a,int b)
{
	long long t=1ll*a*b;
	if(t>=mod)t%=mod;
	return t;
}
inline int dec(int a,int b)
{
	if((a-=b)<0)a+=mod;
	return a;
}
int n,f[400010],ans;
char s[200010],x[400010],t[400010];
vector<int> v;
int main()
{
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;i++)x[i]=s[i];
	for(int i=n+1;i<=n*2;i++)x[i]=(x[i-n]^1);
	for(int i=1;i<=2*n;i++)
		if((2*n)%i==0&&((2*n/i)&1)&&((i&1)==0))v.push_back(i);
	for(int i=0;i<v.size();i++)
	{
		int len=v[i];
		for(int j=1;j<=len/2;j++)t[j]=x[j],f[len]=add(mult(f[len],2),x[j]-'0');
		f[len]=add(f[len],1);
		for(int j=len/2+1;j<=len;j++)t[j]=(x[j-len/2]^1);
		for(int j=len+1;j<=2*n;j++)t[j]=t[j-len];
		if(strcmp(x+1,t+1)==-1)f[len]=dec(f[len],1);
		for(int j=0;j<i;j++)
			if(len%v[j]==0)f[len]=dec(f[len],f[v[j]]);
		ans=add(ans,mult(len,f[len]));
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n, k; scanf("%d%d", &n, &k);
	std::vector<std::pair<int, int>> vec;
	for(int i = 0; i < n; i++) {
		int a, b; scanf("%d%d", &a, &b);
		
		vec.push_back({b, a - 1});
	}
	sort(begin(vec), end(vec)); reverse(begin(vec), end(vec));
	
	i64 A = 0, B = 0, sum = 0, ans = 0, tmp = 0;
	std::priority_queue<i64, std::vector<i64>, std::greater<i64>> qu;
	std::vector<bool> used(n, false);
	for(int i = 0; i < n; i++) {
		if(used[vec[i].second]) {
			sum += vec[i].first;
			qu.push(vec[i].first);
			B++;
		} else {
			used[vec[i].second] = true;
		}
	}
	used = std::vector<bool>(n, false);
	for(int i = 0; i < n; i++) {
		i64 a = vec[i].second, b = vec[i].first;
		if(!used[a]) {
			used[a] = true; A++;
			tmp += b;
		}
		while(!qu.empty() and A + B > k) {
			sum -= qu.top(); qu.pop();
			B--;
		}
		if(A + B == k) {
			ans = std::max(ans, sum + tmp + A * A);
		}
	}
	printf("%lld\n", ans);	
	return 0;
}


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

#define PI acos(-1)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define all(c) (c).begin(), (c).end()
#define TIMESTAMP fprintf(stderr, "Execution time: %.3lf s.\n", 1.0*clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair <int, int> pii;
typedef vector <vi> vvi;
typedef vector <pii> vpii;
typedef vector<string> vs;

const int INF = 100500;
const int MAXN = 1e5 + 9;
const int MOD = 1e9 + 7;

void input() {                  
	int n;
	vi aa;
	cin >> n;
	aa.resize(2 * n);
	for(int i = 0; i < 2 * n; i++) cin >> aa[i];
	sort(all(aa));
	int ans = 0;
	for(int i = 0; i < 2 * n; i += 2) ans += aa[i];
	cout << ans << endl;
}

void solve() {          

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);     
#ifdef LOCAL
	freopen("xxx.in", "r", stdin);
	freopen("xxx.out", "w", stdout);
#else
	//freopen("xxx.in", "r", stdin);
	//freopen("xxx.out", "w", stdout);
#endif	
	input();
	solve();
	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 rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main() {
    ll a;
    double b;
    cin >> a >> b;
	int c = round(100*b);
	
    cout << a*c/100 << endl;
	return;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 3704
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

/*
dpx[i+1][j] = dpx[i][j-a[i]] | dpx[i][j+a[i]];
*/
int dpx[8100][20000], dpy[8100][20000];

int main() {
  int x,y;
  string s;
  cin >> s;
  cin >> x >> y;
  vi X,Y;
  int cnt = 0, k = 0;
  s.push_back('T');
  int n = sz(s);
  rep(i,n){
    if(s[i] == 'T'){
      if(cnt || i == 0){
        if(k) Y.push_back(cnt);
        else X.push_back(cnt);
        cnt = 0;
      }
      k^=1;
      
    }
    else{
      cnt++;
    }
  }

  dpx[0][8000] = 1, dpy[0][8000] = 1;
  rep(i,sz(X)){
    if(i == 0){
        dpx[i+1][8000+X[i]] = 1;
        continue;
    }
    rep(j,16001){
      if(j-X[i] >= 0)dpx[i+1][j] |= dpx[i][j-X[i]];
      if(j-X[i] <= 16000)dpx[i+1][j] |= dpx[i][j+X[i]];
    }
  }
  rep(i,sz(Y)){
    rep(j,16001){
      if(j-Y[i] >= 0)dpy[i+1][j] |= dpy[i][j-Y[i]];
      if(j-Y[i] <= 16000)dpy[i+1][j] |= dpy[i][j+Y[i]];
    }
  }
  // rep(i,sz(X))show(X[i]);
  // rep(i,sz(X)){
  //   rep(j,16000){
  //     cout<<dpx[i][j] << " ";
  //   }
  //   cout<<endl;
  // }
  if(dpx[sz(X)][8000+x] && dpy[sz(Y)][8000+y]){
    print("Yes");
  }
  else print("No");

  return 0;
}

Measured memory_bytes: 315264
#include<iostream>
#include<iomanip>
#include<complex>
#include<cmath>
using namespace std;
typedef complex<double> xy_t;

void kock(int, xy_t, xy_t);
void print(xy_t);
int main() {
	int n;
	cin >> n;
	xy_t p1(0,0), p2(100,0);
	print(p1);
	kock(n, p1, p2);
	print(p2);
}

void kock(int n, xy_t p1, xy_t p2) {
	if (n == 0) return;
	xy_t s, t, u;
	s = (p1 * xy_t(2,0) + p2) / xy_t(3.0,0);
	t = (p1 + p2 * xy_t(2,0)) / xy_t(3.0,0);
	u = s + (t - s)* xy_t(cos(M_PI / 3.0), sin(M_PI / 3.0));


	kock(n - 1, p1, s);
	print(s);
	kock(n - 1, s, u);
	print(u);
	kock(n - 1, u, t);
	print(t);
	kock(n - 1, t, p2);
}

void print(xy_t z) {
	cout << fixed << setprecision(6) << z.real() << " " << z.imag() << endl;
}

Measured memory_bytes: 3236
#include <iostream>
#include <string>

using namespace std;

string field[12];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
void crash_island(int y, int x) {
    field[y][x] = '0';
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0) continue;
        if (ny < 0) continue;
        if (12 <= nx) continue;
        if (12 <= ny) continue;
        if (field[ny][nx] == '1') {
            crash_island(ny, nx);
        }
    }
}

int solve() {
    int count = 0;
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 12; j++) {
            if (field[i][j] == '1') {
                crash_island(i, j);
//                cout << "i: " << i << endl;
//                for (int i = 0; i < 12; i++) {
//                    cout << field[i] << endl;
//                }
                count++;
            }
        }
    }
    return count;
}

int main() {
    while (cin >> field[0]) {
        for (int i = 1; i < 12; i++) {
            cin >> field[i];
        }  
        cout << solve() << endl;
    }
    return 0;
}

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

using i64 = int64_t;

int main(){
    i64 x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<i64> vx, vy, vz;
    for(int i=0;i<x;++i){
        i64 tmp;
        cin >> tmp;
        vx.push_back(tmp);
    }
    for(int i=0;i<y;++i){
        i64 tmp;
        cin >> tmp;
        vy.push_back(tmp);
    }
    for(int i=0;i<z;++i){
        i64 tmp;
        cin >> tmp;
        vz.push_back(tmp);
    }
    vector<i64> v;
    for(int i=0;i<x;++i){
        for(int j=0;j<y;++j){
            v.push_back(vx[i]+vy[j]);
        }
    }
    sort(v.rbegin(), v.rend());

    vector<i64> ans;
    for(int i=0;i<min(k,(i64)v.size());++i){
        for(int j=0;j<z;++j){
            ans.push_back(v[i]+vz[j]);
        }
    }
    sort(ans.rbegin(), ans.rend());

    for(int i=0;i<k;++i)cout << ans[i] << endl;

    return 0;
}


Measured memory_bytes: 42616
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int k = stdIn.nextInt();
        int p[] = new int[n];
        
        double max = 0;
        int sum = 0;
        
        for(int i = 0; i < n; i++){
            p[i] = stdIn.nextInt();
            if(i < k){
                sum += p[i];
            }
        }
        
        max = sum;
        int index = 0;
        
        for(int i = k; i < n; i++){
            sum -= p[i - k];
            sum += p[i];
            if(sum > max){
                max = sum;
                index = i - k;
            }
        }
        
        double kitaichi = max / 2 + 0.5 * k;

        System.out.println(kitaichi);
        
        
    }
}


Measured memory_bytes: 82092
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define print(A,n) for(ll i=0;i<n;++i)cout<<A[i]<<' ';cout<<endl;
#define take(A,n) for(ll i=0;i<n;++i)cin>>A[i];
//    for(auto& it : m)
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
//  priority_queue<ll int> pq;
//  priority_queue <ll int, vector<ll int>, greater<ll int> > pq;
//  vector<ll int> v;
//  vector< pair<ll int,ll int> > v;
//  set<ll int>::iterator it=s.begin();
//  unordered_map<  pair<ll int,ll int>, ll int> mp;
 
 
 
int main()
{
  fastio();
 
ll int T=1;
//cin>>T;
while(T--)
{
  ll int a,b,m,i,mina=INT_MAX,minb=INT_MAX;
  cin>>a>>b>>m;
  ll int aa[a],bb[b];
  for(i=0;i<a;i++)
  {
      cin>>aa[i];
      mina=min(mina,aa[i]);
  }
  for(i=0;i<b;i++)
  {
      cin>>bb[i];
      minb=min(minb,bb[i]);
     
  }
  ll int ans= minb+mina,x,y,z;
  for(i=0;i<m;i++)
  {
      cin>>x>>y>>z;
      ans=min(aa[x-1]+bb[y-1]-z,ans);
  }
  cout<<ans<<endl;
}
    return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;
 
 
public class Main{
     
	public static int cat(char[] input, int start, int end){
		if(input[start] != 'm'){
			return start;
		}
		
		int might_e = cat(input, start + 1, end);
		
		if(input[might_e] != 'e'){
			return might_e;
		}
		
		int might_w = cat(input, might_e + 1, end);
		
		if(input[might_w] != 'w'){
			return might_w;
		}
		
		return might_w + 1;
	}
	
    public static void main(String[] args){
    	
    	final Scanner sc = new Scanner(System.in);
    	
    	char[] input = sc.next().toCharArray();
    	
    	final int ret = cat(input, 0, input.length - 1);
    	
    	if(ret == input.length){
    		System.out.println("Cat");
    	}else{
    		System.out.println("Rabbit");
    	}
    	
    }
     
}

Measured memory_bytes: 17288
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
/*----------------------------------------------------------------------------------*/


int main() {
    ll n, a, b; cin >> n >> a >> b;
    vector<ll> x(n);
    rep(i,n) cin >> x[i];

    ll ans = 0;
    repf(i,1,n) {
        if ((x[i]-x[i-1])*a > b) {
            ans += b;
        } else {
            ans += a*(x[i]-x[i-1]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <iterator>
#include <math.h>
#include <cstdlib>
#include <cmath>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define dump(x)  cerr << #x << " = " << (x) << endl;
using namespace std;
int main(){
  int H,W;
  cin >> H >> W;
  char s[H][W];
  FOR(i,0,H){
    FOR(j,0,W){
      cin >> s[i][j];
    }
  }
  bool ans = true;
  FOR(i,0,H){
    FOR(j,0,W){
      if(s[i][j] == '#'){
        bool flag = false;
        if(i - 1 >= 0 && s[i -1][j] == '#') flag = true;
        if(i + 1 < H && s[i +1][j] == '#') flag = true;
        if(j - 1 >= 0 && s[i][j - 1] == '#') flag = true;
        if(j + 1 < W && s[i][j + 1] == '#') flag = true;
        if(!flag) ans = false;
      }
    }
  }
  if(ans){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string>
#include<complex>
#include<algorithm>

long long gcd(long long d, long long x)
{
	while (x % d)
	{
		x %= d;
		std::swap(d, x);
	}
	return d;
}

int main()
{
	int n;
	long long X, x[100000], d;
	scanf("%d%lld", &n, &X);
	for (int i = 0; i < n; ++i)
	{
		scanf("%lld", x + i);
		x[i] = std::abs(x[i] - X);
		if (i)
			d = gcd(d, x[i]);
		else
			d = x[i];
	}

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

	return 0;
}

Measured memory_bytes: 1024
values = [int(c) for c in input()]
for i in range(8):
  if values[0] + sum([[1, -1][(i >> j) & 1] * values[j + 1] for j in range(3)]) == 7:
    print(str(values[0]) + ''.join([['+', '-'][(i >> j) & 1] + str(values[j + 1]) for j in range(3)]) + '=7')
    break


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

const int MXN = (1 << 4);

int n, in[MXN][MXN];
long long dp[1 << MXN], pp[1 << MXN];

void npt() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> in[i][j];
		}
	}
}

void rec(int i, const vector<int>& nt, long long sc, int msk, int gp) {
	if (i == (int) nt.size()) {
		dp[msk] = max(dp[msk], sc + pp[gp]);
		return ;
	}
	rec(i + 1, nt, sc, msk, gp);
	rec(i + 1, nt, sc, msk ^ (1 << nt[i]), gp ^ (1 << nt[i]));
}

void slv() {
	for (int i = 1; i <= n; i++)
		dp[i] = INT_MIN;
	dp[0] = 0;
	for (int msk = 0; msk < (1 << n); msk++)
		for (int i = 0; i < n; i++)
			if (msk & (1 << i))
				for (int j = i + 1; j < n; j++)
					if (msk & (1 << j))
						pp[msk] += in[i][j];
	for (int msk = 0; msk < (1 << n); msk++) {
		vector<int> nt;
		for (int i =  0; i < n; i++)
			if (!(msk &  (1 << i)))
				nt.push_back(i);
		rec(0, nt, dp[msk], msk, 0);
	}
}

void tpt() {
	cout << dp[(1 << n) - 1] << endl;
}

int main() {
	npt();
	slv();
	tpt();
	return 0;
}


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

#define ll long long

int main(){

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false); 

	ll a, b, c, k;
	cin >> a >> b >> c >> k;
	ll sum = 0;
	if (a >= k && k > 0){
		sum+=k;
		k = 0;
	} else if (a < k && k > 0) {
		sum+=a;
		k-=a;
	}

	if (b >= k && k > 0){
		k = 0;
	} else if (b < k && k > 0) {
		k-=b;
	}

	if (c >= k && k > 0){
		sum-=k;
		k = 0;
	} else if (c < k && k > 0) {
		sum-=c;
		k-=c;
	}

	cout << sum;





}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mod 1000000007
int main()
{
    int n;
    cin>>n;
    lli h[n],cost[n];
    for(int i=0;i<n;i++) cin>>h[i];
    for(int j=0;j<n;j++) cin>>cost[j];
    vector<lli> dp(n+1);
    int base=1;
    while(base<=n) base*=2;
    vector<lli> tree(2*base);
    for(int i=0;i<n;i++)
    {
        lli mx=0;
        int index=h[i]+base;
        while(index>1)
        {
            if(index%2==1) mx=max(mx,tree[index-1]);
            index/=2;
        }
        dp[h[i]]=cost[i]+mx;
        for(int index=h[i]+base;index>=1;index/=2)
        {
            tree[index]=max(tree[index],dp[h[i]]);
        }
        /*for(int j=0;j<h[i];j++)
        {
            dp[h[i]]=max(dp[h[i]],dp[j]+cost[i]);
        }*/
    }
    lli mx=INT_MIN;
    for(int i=0;i<=n;i++) mx=max(mx,dp[i]);
    cout<<mx<<endl;
    return 0;
}

Measured memory_bytes: 9088
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar(n) array<int,n>
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin>>s;
	ll k =0;
	for(int i =0; i<pow(2,s.size()-1);i++)
	{
		string t =s;
		for(int j = s.size()-2; j>=0; j--)
		{
			if(i>>j & 1) t.insert(t.begin()+j+1,' ');
		}
		stringstream ss(t);
		ll x =0;
		while(ss>>x)
			k += x;
	}
	cout<<k<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
vector<ll>vec;
ll val[3009][3009];
ll dp[3009][3009][4];
ll n,m;
ll call(ll a,ll b,ll c)
{
    if(b>m)
    {
        return 0;
    }
    if(a>n)
    {
        return 0;
    }
    if(dp[a][b][c]!=-1)
    {
        return dp[a][b][c];
    }
    ll x,y;
    x=y=0;
    if(c<2)
    {
        x=val[a][b]+call(a,b+1,c+1);
        y=val[a][b]+call(a+1,b,0);
        x=max(x,y);
        y=call(a,b+1,c);
        x=max(x,y);
    }
    else
    {
        x=val[a][b]+call(a+1,b,0);
        y=call(a,b+1,c);
        x=max(x,y);
    }

    return dp[a][b][c]=x;

}
int main()
{
    ll a,b,c,d,e,i,j,k,l,x,y,t,p,r;
    cin>>n>>m>>k;
    for(i=1;i<=k;i++)
    {
        cin>>a>>b>>c;
        val[a][b]=c;
    }
    memset(dp,-1,sizeof(dp));
    x=call(1,1,0);
    cout<<x<<endl;
}



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

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

    vector<int> A(N), B(N), C(N);
    rep(i, N) {
        cin >> A[i];
        A[i]--;
    }
    rep(i, N) cin >> B[i];
    rep(i, N-1) cin >> C[i];

    int ans = 0;
    int prev = -1;
    rep(i, N) {
        ans += B[A[i]];
        if (prev != -1 and A[i] - prev == 1) {
            ans += C[prev];
        }
        prev = A[i];
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);   

int main(){
    std::ios::sync_with_stdio(false);
    int a,b,c;
    int ans;
    cin>>a>>b>>c;
    if(a<b){
    	swap(a,b);
    }
    if(a<c){
    	swap(a,c);
    }
    ans=2*a-b-c;
    if(ans%2){
    	ans+=3;
    }
    ans/=2;
    cout<<ans<<endl;
    return 0;  
    
}



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

int main(){
    long double w, h, x, y;
    cin >> w >> h >> x >> y;

    if(x == w/2 && y == h/2)
        cout << setprecision(10) << w*h/2 << " " << 1 << endl;
    else
        cout << setprecision(10) << w*h/2 << " " << 0 << endl;

}

Measured memory_bytes: 256
s=input()
if s=='SUN':
  print(7)
elif s=='MON':
  print(6)
elif s=='TUE':
  print(5)
elif s=='WED':
  print(4)
elif s=='THU':
  print(3)
elif s=='FRI':
  print(2)
else:
  print(1)

Measured memory_bytes: 38256
import java.util.Scanner;

public class Main {

	public static void main(String args[]){

		Scanner cin = new Scanner(System.in);

		int target = cin.nextInt();
		cin.close();
		String result ="ABC";
		if(target>=1200){
			result = "ARC";
		}
		System.out.println(result);

	}
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll inf  = 1e6+5;
vector<int> freq (5);
int main() {
  string s; cin >> s;
  set<char> ss;
  for (char i : s){
      ss.insert(i);
  }
  if (ss.size() > 1){
      cout << "Yes";
  }
  else{
      cout << "No";
  }
}

Measured memory_bytes: 256
N,K = map(int,input().split())
ruiseki = [0]*(N+1)
now = 0
maximum = -999999999
ans = 0
p = list(map(int,input().split()))
for i in range(N):
    now += p[i]
    ruiseki[i+1] = now
for i in range(0,N-K+1):
    P = ruiseki[i+K]-ruiseki[i]
    if P > maximum:
        maximum = P
        Q = p[i:i+K]
for i in range(len(Q)):
    ans += (0.5*Q[i]*(Q[i]+1))/Q[i]
print(ans)

Measured memory_bytes: 26912
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
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(){
    ll N;
    cin>>N;
    vector<ll>B(100001,0);
    ll sum=0;
    rep(i,N){
        ll a;
        cin>>a;
        sum+=a;
        B[a]+=1;
    }
    ll Q;
    cin>>Q;
    rep(i,Q){
        ll D,C;
        cin>>D>>C;
        ll S=B[D];
        sum-=D*S;
        sum+=C*S;
        B[C]+=S;
        B[D]-=S;
        cout<<sum<<endl;
    }
}

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

int sum(int h[], int n, int x, int a[]){
	if(n == 1) return 0;
	else if(n == 2) return abs(h[x] - h[x + 1]);
	else if(a[x] != -1) return a[x];
	else{
		if(a[x + 1] == -1){
			a[x + 1] = sum(h, n - 1, x + 1, a);
		}
		if(a[x + 2] == -1){
			a[x + 2] = sum(h, n - 2, x + 2, a);
		}
		return min(abs(h[x] - h[x + 1]) + a[x + 1], abs(h[x] - h[x + 2]) + a[x + 2]);
	}
}

int main(){
	int n;
	cin >> n;
	int h[n], a[n];
	for(int i = 0; i < n; i++){
		cin >> h[i];
		a[i] = -1;
	}
	
	cout << sum(h, n, 0, a);
	return 0;
}

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

int main() {
  int N, K; cin >> N >> K;
  int A[N]; for (int i = 0; i < N; i++) cin >> A[i];
  int l = 1, r = 1e+9;
  while (l < r) {
    int m = (l + r) / 2, k = 0;
    for (int i = 0; i < N; i++) k += (A[i] - 1) / m;
    if (k <= K) r = m;
    else l = m + 1;
  }
  cout << r << endl;
}

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

int main(){
	int N,a,b;
	long long K,count[100010]={};
	cin >> N >> K;

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

	for(int j=0; j<=100000; j++){
		if(K<=count[j]){
			cout << j << endl;
			break;
		}
		K -= count[j];
	}
}

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



int main(void){
    int N,M;
    cin>>N>>M;
    vector<int> X(M);
    for(int i=0;i<M;i++){
        cin>>X[i];
    }
    sort(X.begin(),X.end());
    int ans=0;
    if(N>=M) {
        cout<<ans<<endl;
    }else{
        ans=X[M-1]-X[0];
        vector<int> dis(M-1);
        for(int i=0;i<M-1;i++){
            dis[i]=X[i+1]-X[i];
        }
        sort(dis.begin(),dis.end(),greater<int>());
        for(int i=0;i<N-1;i++){
            ans-=dis[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long int
#define PI 3.1415926
using namespace std;
const int N=1e6+1;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll x,p=100,ans=0;cin>>x;
    while(p<x)
    {
        p+=p/100;
        ans++;
    }
    cout<<ans;
}


Measured memory_bytes: 3640
N,M,K = map(int,input().split())
MOD = 998244353
ans = 0


fact = [1] * (N+1) # 階乗を格納するリスト
factinv = [1] * (N+1) # 階乗を格納するリスト



for i in range(N):
    fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算
    factinv[i+1] = pow(fact[i+1], MOD-2, MOD)# MODを法とした逆元

def nCk(n,k): # 組み合わせ(MOD)を返却する
    return fact[n] * factinv[n-k] * factinv[k] % MOD

def solve(k):
    r = M * pow(M-1,N-1-k,MOD) * nCk(N-1,k)
    return r

for k in range(K+1):
    ans += solve(k)
    ans %= MOD
print (ans)

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

int main(){
  int s,f=0,l=0;
  cin >> s;
  
  f = s/100;
  l = s%100;
  
  if(1<=f&&f<=12  && 1<=l&&l<=12){
    cout << "AMBIGUOUS" << endl;
  } else if(1<=f&&f<=12){
    cout << "MMYY" << endl;
  } else if(1<=l&&l<=12){
    cout << "YYMM" << endl;
  } else{
    cout << "NA" << endl;
  }
}


Measured memory_bytes: 256
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
MOD = 10 ** 9 + 7
dp = [[0] * W for _ in range(H+1)]
dp[0][0] = 1
ladder = [[0] * 2 for _ in range(15)] #あえて多めに用意
ladder[1][0] = 1
for i in range(2, 9):
    ladder[i][0] = ladder[i-1][0] + ladder[i-1][1]
    ladder[i][1] = ladder[i-1][0]

ladder = [max(1, x+y) for x, y in ladder]

for i in range(1, H+1):
    for j in range(W):
        dp[i][j] += dp[i-1][j] * ladder[W-j-1] * ladder[j]
        if j > 0:
            dp[i][j] += dp[i-1][j-1] * ladder[W-j-1] * ladder[j-1]
        if j < W-1:
            dp[i][j] += dp[i-1][j+1] * ladder[W-j-2] * ladder[j]
        dp[i][j] %= MOD

print(dp[H][K-1] % MOD)
# 52

Measured memory_bytes: 38256
import numpy as np

N, K = map(int, input().split())
p = np.array(list(map(int, input().split())))
ans = tmp = np.sum((p[0:K]+1)/2)

for n in range(1, N-K+1):
	last = (p[n-1]+1)/2
	next = (p[n+K-1]+1)/2
	tmp = tmp - last + next
	if ans < tmp:
		ans = tmp

print(ans)

Measured memory_bytes: 33992
//
// Created by maze on 2019/09/15.
//

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

#define INF_LL (int64)1e18
#define INF (int64)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define lp(i,n) for(int i=0;i<n;i++)
#define FOR(i, a, b) for(int64 i = (a); i < (b); i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int32_t;
using int64 = int64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

int rc[100001];
int cc[100001];

class UnionFind{
private:
    vector<int_fast32_t> par;
    size_t n;

public:
    UnionFind(){}
    UnionFind(size_t n):n(n){
        par.resize(n,-1);
    }

    uint_fast32_t find(uint_fast32_t x){
        return par[x]<0?x:par[x]=find(par[x]);

    }

    size_t size(uint_fast32_t x){
        return -par[find(x)];
    }

    bool unite(uint_fast32_t x,uint_fast32_t y){
        x=find(x);
        y=find(y);
        if(x==y)return false;
        if(size(x)<size(y))swap(x,y);
        par[x]+=par[y];
        par[y] =x;
        return true;
    }

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

int main(void) {
    int n;
    cin>>n;
    int cnt=0;
    UnionFind uf(n);
    lp(i,n){
        int a,b;
        cin>>a>>b;
        rc[a]++;
        cc[b]++;
        uf.unite(a-1,b-1);
    }
    bool b=true;
    lp(i,n){
        if(rc[i+1]!=1)b=false;
        if(cc[i+1]!=1)b=false;
    }
    int ans=0;
    if(b==false)cout<<-1<<endl;
    else {
        lp(i,n){
            if(uf.find(i)==i){
                ans+=uf.size(i)-1;
            }
        }
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 4392
#include <iostream>
using namespace std;
int main(void){
    // Your code here
    int a, b;scanf("%d%d",&a,&b);
    int c[b], d[b];
    for (int i =0; i<b; i++){scanf("%d%d",&c[i],&d[i]);}
    
    // 最小値と最大値の区切りを更新するアルゴリズム
    int start = c[0];
    int end = d[0];
    for (int j = 1; j < b; j++){
        if (c[j] > start){
            start = c[j];
        }
        if (d[j] < end){
            end = d[j];
        }
    }
    
    int result = max(0, (end - start + 1));
    printf("%d", result);

}

Measured memory_bytes: 4596