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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];
    vector<int> B(M);
    for(int i=0; i<M; i++) cin >> B[i];

    auto C = atcoder::convolution(A, B);
    for(int i=0; i<C.size(); i++)
    {
        if(i != 0) cout << ' ';
        cout << C[i];
    }
    cout << '\n';

    return 0;
}


Measured memory_bytes: 19000
n=int(input())
h=list(map(int,input().split()))

dp = [-1]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
if n == 2:
  print(dp[1])
  exit()
for i in range(2,n):
  dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[n-1])


Measured memory_bytes: 13980
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>
#include<unordered_map>
#include<deque>
#include<cmath>





using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const ll INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
//const ll mod = 1000 * 1000 * 1000 + 7;




void solve() {
    int n;
    cin >> n;
    ll x, y;
    x = 1, y = 1;
    ll a, b;
    for (int i = 0; i < n; ++i) {
        cin >> a >> b;
        ll q = max((x + a - 1) / a, (y + b - 1) / b);
        x = a * q, y = b * q;
    }
    cout << x + y << endl;

}


//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    solve();



#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}


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

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN = 1e3 + 5;


char tb[MAXN][MAXN];
int dist[MAXN][MAXN];
bool used[MAXN][MAXN];
int n, m;
int stx, sty, edx, edy;
vector<pair<int, int>> steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

bool check_cell(int i, int j) {
    return (i >= 0 && j >= 0 && j < m && i < n && tb[i][j] == '.');
}

void solve() {
    cin >> n >> m;
    cin >> stx >> sty >> edx >> edy; --stx; --sty; --edy; --edx;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> tb[i][j];
            dist[i][j] = 1e9;
        }
    }
    dist[stx][sty] = 0;
    deque<pair<int, int>> q;
    q.push_back({stx, sty});
    while (!q.empty()) {
        auto top = q.front();
        q.pop_front();
        used[top.first][top.second] = true;
        if (top.first == edx && top.second == edy) {
            cout << dist[top.first][top.second] << "\n";
            return;
        }
        for (auto step : steps) {
            int newi = step.first + top.first, newj = step.second + top.second;
            if (check_cell(newi, newj) && !used[newi][newj] && dist[newi][newj] > dist[top.first][top.second]) {
                q.push_front({newi, newj});
                dist[newi][newj] = dist[top.first][top.second];
            }
        }
        for (int dx = -2; dx <= 2; ++dx) {
            for (int dy = -2; dy <= 2; ++dy) {
                int newi = top.first + dx, newj = top.second + dy;
                if (check_cell(newi, newj) && !used[newi][newj] && dist[newi][newj] > dist[top.first][top.second] + 1) {
                    dist[newi][newj] = dist[top.first][top.second] + 1;
                    q.push_back({newi, newj});
                }
            }
        }
    }
    cout << -1 << "\n";
}

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

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

int main() {
	int n,k;
	cin >> n >> k;
	vector<int> h(n,0);
	for(int i;i < n;i++)
	{
		cin >> h.at(i);
	}
	long long sm = 0;
	if(n <= k)
	{
		sm = 0;
	}
	else
	{
		sort(h.begin(),h.end());
		for(int i = 0;i < n - k;i++)
		{
			sm += h.at(i);
		}
	}
	cout << sm <<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <cmath>
#include <stdio.h>
#include <float.h>

using namespace std;

int main() {
    int N, K;scanf("%d%d", &N, &K);
    double s = 0;
    for (int i = 1; i < N+1; ++i) { 
        double tmp = 1.0/N;
        int now=i;
        while(now < K) {
            now *= 2;
            tmp /= 2;
        }
        s += tmp;
    }
    printf("%.12f\n", s);
    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

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

int main()
{   
    int n;
    cin >> n;
    vi a(n+1);
    rep(i, n) cin >> a[i+1];

    vi b(n+1);
    for(int i = n; i >= 1; i--) {
        int sum = 0;
        for(int j = i+i; j <= n; j += i) {
            sum ^= b[j];
        }
        b[i] = sum^a[i];
    }

    vi ans;
    rep(i,n+1) if(b[i]) ans.push_back(i);

    cout << ans.size() << endl;
    for(auto x : ans) cout << x << endl;

    return 0;
}


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

#define PI 4*atan(1)
#define INF 1e8

typedef long long ll;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
  string s;
  cin >> s;
  string ans = "";
  for(int i = 0; i < s.size(); i++){
    if(i % 2 == 0)ans += s[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main() {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int x3, y3, x4, y4;
	vector<int> xy = { x2 - x1, y2 - y1 };
	x3 = x2 - xy.at(1);
	y3 = y2 + xy.at(0);
	x4 = x3 - xy.at(0);
	y4 = y3 - xy.at(1);

	cout << x3 <<" "<< y3 << " " << x4 << " " << y4 << " " << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int a,b,i,j,k,sum=0,s[6];
    scanf("%d %d",&a,&b);
    for(i=a;i<=b;i++)
    {
        j=0;
        k=i;
        while(k)
        {
            s[j++]=k%10;
            k=k/10;
        }
        if(s[0]==s[4]&&s[1]==s[3])
            sum=sum+1;
        memset(s,0,sizeof(s));
    }
    printf("%d",sum);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod=1000000007;
const int INF=1001001001;

vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  string S;
  cin>>S;
  int sum=0;
  for(int i=0;i<S.size();i++){
    sum+=S[i]-'0';
  }
  if(sum%9==0){cout<<"Yes"<<endl;}
  else{cout<<"No"<<endl;}
  return 0;  
}

Measured memory_bytes: 3724
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <ctime>
#include <unordered_map>
#include <iomanip>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;

int H,W,dp[2010][2010][2]; char a[2010][2010];
int l[2010],r[2010],v[2010],st[2010],K;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> H >> W;

    int i,j,res=max(H,W);
    for (i=1; i<=H; i++)
        for (j=1; j<=W; j++)
            cin >> a[i][j];

    for (i=1; i<=H; i++)
        for (j=1; j<W; j++){
            if (a[i][j]==a[i][j+1]) dp[i][j][0]=1+dp[i-1][j][0];
            else dp[i][j][0]=0;

            if (a[i][j]!=a[i][j+1]) dp[i][j][1]=1+dp[i-1][j][1];
            else dp[i][j][1]=0;
        }

    for (i=1; i<=H; i++){
        for (j=1; j<W; j++)
            v[j]=max(dp[i][j][0],dp[i][j][1]);

        K=0;
        for (j=1; j<W; j++){
            while (K && v[st[K]]>=v[j])
                K--;

            if (K) l[j]=st[K]+1;
            else l[j]=1;
            st[++K]=j;
        }

        K=0;
        for (j=W-1; j>0; j--){
            while (K && v[st[K]]>=v[j])
                K--;

            if (K) r[j]=st[K]-1;
            else r[j]=W-1;
            st[++K]=j;
        }

        for (j=1; j<W; j++)
            res=max(res,(r[j]-l[j]+2)*v[j]);

    }

    cout << res << "\n";
    return 0;
}


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

int main(void){

  int H = 1, W = 1;
  int i, j;

  while(H > 0 || W > 0){
    scanf("%d %d", &H, &W);
    if(H == 0 && W == 0){
      break;
    }else{
      if(H % 2 == 0){
	if(W % 2 == 0){
	  for(i = 0; i < H / 2; i++){
	    for(j = 0; j < W / 2; j++){
	      printf("#.");
	    }
	    printf("\n");
	    for(j = 0; j < W / 2; j++){
	      printf(".#");
	    }
	    printf("\n");
	  }
	}else{
	  for(i = 0; i < H / 2; i++){
	    for(j = 0; j < (W - 1) / 2; j++){
	      printf("#.");
	    }
	    printf("#\n");
	    for(j = 0; j < (W - 1) / 2; j++){
	      printf(".#");
	    }
	    printf(".\n");
	  }
	}
      }else{
	if(W % 2 == 0){
	  for(i = 0; i < (H - 1) / 2; i++){
	    for(j = 0; j < W / 2; j++){
	      printf("#.");
	    }
	    printf("\n");
	    for(j = 0; j < W / 2; j++){
	      printf(".#");
	    }
	    printf("\n");
	  }
	  for(j = 0; j < W / 2; j++){
	    printf("#.");
	  }
	  printf("\n");
	}else{
	  for(i = 0; i < (H - 1) / 2; i++){
	    for(j = 0; j < (W - 1) / 2; j++){
	      printf("#.");
	    }
	    printf("#\n");
	    for(j = 0; j < (W - 1) / 2; j++){
	      printf(".#");
	    }
	    printf(".\n");
	  }
	  for(j = 0; j < (W - 1) / 2; j++){
	    printf("#.");
	  }
	  printf("#\n");
	}
      }
    }
    printf("\n");
  }
  
  return 0;
}


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

int main() {
    int n,t; cin >> n >> t;
    int a[100000];
    rep(i,n) cin >> a[i];
    int hiRight[100001] = {0};
    rep(i,n) hiRight[n-i-1] = max(hiRight[n-i],a[n-i-1]);
    int cnt,hi;
    cnt = hi = 0;
    rep(i,n) {
        if (hiRight[i] - a[i] > hi) {
            hi = hiRight[i] - a[i];
            cnt = 1;
        }
        else if (hiRight[i] - a[i] == hi) cnt ++;
    }
    cout << cnt << endl;
}


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

int main(){
  int K,S,i,ans=0,k,Zap;
  cin >> K >> S;
  
  for(i=0; i<=K; i++){
    for(k=0; k<=S-i; k++){
      if(k > K){
        continue;
      }
        Zap=S-i-k;
      if(Zap > K){
        continue;
      }
      ans += 1;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	string s;cin>>s;
	int n=s.size();int keep[2019]={};
	//余りを累積和すればいける
	keep[0]=1;
	int a[n+1];a[0]=0;//その桁が追加されるといくつ余りが増えるか
	ll md=2019;
	int ans=0;
	int j=1;
	for(int i=0;i<n;i++){//下から何桁取るか考える
		ll t=s[n-i-1]-'0',tt=s[n-i-1]-'0';
		t=t*j%md;
		a[i+1]=(t+a[i])%md;
		//数え上げ
		int l=a[i+1];
		keep[l]++;
		//cout<<keep[l]<<" "<<keep0[l]<<"\n";
		
		if(tt!=0) ans+=keep[l]-1;
		//cout<<a[i+1]<<"\n";
		j=(j*10)%md;
	}

	cout<<ans<<"\n";
}

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef long long LL;
#define REP(i,s,N) for (int i=s; i<N; i++)

string IntToString(int number) {
	stringstream ss;
	ss << number;
	return ss.str();
}

int main() {
	string A, B;
	cin >> A >> B;
	if(A.size()==B.size()){
		REP(i,0,A.size()){
			if(A[i]<B[i]) {
				cout << "LESS" << endl;
				return 0;
			}
			else if(A[i]>B[i]) {
				cout << "GREATER" << endl;
				return 0;
			}
		}
	}
	else if(A.size() > B.size()) {
		cout << "GREATER" << endl;
		return 0;
	}
	else {
		cout << "LESS" << endl;
		return 0;
	}
	cout << "EQUAL" << endl;
	return 0;
}

Measured memory_bytes: 256
//
// Created by yamunaku on 2020/04/19.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 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)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

vi c;
mti e;
vl cnt;
vl ans;

ll dfs(int x, int p){
    int sz = 1;
    for(auto &nx : e[x]){
        if(nx == p) continue;
        ll k = cnt[c[x]];
        ll ret = dfs(nx, x);
        sz += ret;
        ll t = ret - (cnt[c[x]] - k);
        ans[c[x]] += t * (t + 1) / 2;
        cnt[c[x]] = k + ret;
    }
    cnt[c[x]]++;
    return sz;
}

int main(){
    //CFS;
    ll n;
    cin >> n;
    c = vi(n);
    rep(i, n) cin >> c[i], c[i]--;
    e = mti(n);
    int u, v;
    rep(i, n - 1){
        cin >> u >> v;
        u--, v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    cnt = ans = vl(n);
    dfs(0, 0);
    rep(i, n){
        ans[i] += (n - cnt[i]) * (n - cnt[i] + 1) / 2;
        cout << n * (n + 1) / 2 - ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 33464
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	Scanner in = new Scanner(System.in);
	int h, w;
	int[] minX = new int[26], minY = new int[26];
	int[] maxX = new int[26], maxY = new int[26];
	boolean[][] covered = new boolean[26][26];
	char[][] result;
	boolean ans;
	
	public void run() {
		int n = in.nextInt();
		for (int loopN = 0; loopN < n; loopN++) {
			ans = true;
			h = in.nextInt(); w = in.nextInt();
			Arrays.fill(maxX, -1);
			Arrays.fill(maxY, -1);
			Arrays.fill(minX, 101);
			Arrays.fill(minY, 101);
			for (int i = 0; i < covered.length; i++) {
				Arrays.fill(covered[i], false);
			}
			
			result = new char[h][w];
			for (int i = 0; i < h; i++) {
				result[i] = in.next().toCharArray();
				for (int j = 0; j < w; j++) {
					if (result[i][j] == '.') continue;
					int index = result[i][j] - 'A';
					minX[index] = Math.min(j, minX[index]);
					minY[index] = Math.min(i, minY[index]);
					maxX[index] = Math.max(j, maxX[index]);
					maxY[index] = Math.max(i, maxY[index]);
				}
			}
			
			end : for (int i = 0; i < maxX.length; i++) {
				if (minX[i] == 101 || maxX[i] == -1 || minY[i] == 101 || maxY[i] == -1)
					continue;
				
				for (int j = minY[i]; j <= maxY[i]; j++) {
					for (int k = minX[i]; k <= maxX[i]; k++) {
						if (result[j][k] == '.') {
							ans = false;
							break end;
						}
						int c = result[j][k] - 'A';
						if (i != c) {
							if (isCovered(i, c)) {
								ans = false;
								break end;
							}
						}
					}
				}
			}
			
			System.out.println((ans) ? "SAFE" : "SUSPICIOUS");
		}
	}
	
	public boolean isCovered(int c1, int c2) {
		if (covered[c1][c2]) return true;
		
		for (int i = 0; i < covered.length; i++) {
			if (covered[c1][i]) {
				if (isCovered(i, c2)) return true;
			}
		}
		
		covered[c2][c1] = true;
		return false;
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

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

int main()
{
    ll n;
    cin >> n;
    map<ll, ll> cnt;
    vector<ll> arr(n);
    for (int i = 0; i < n; i++)
    {
        ll t;
        cin >> t;
        cnt[t]++;
        arr[i] = t;
    }
    ll res = 0;
    for (auto k : cnt)
    {
        if (k.second > 1)
        {
            res += k.second * (k.second - 1) / 2;
        }
    }
    for (int i = 0; i < n; i++)
    {
        ll temp = res;
        temp -= cnt[arr[i]] - 1;
        cout << temp << endl;
    }
    return 0;
}

Measured memory_bytes: 11008
class segtree:
  #セグメント木
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    return s.d[p + s.size]
 
  # 区間演算
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
 
import sys
    
def e():
  return 0
 
def op(s, t):
  return max(s, t)
 
N, Q = list(map(int, input().split()))
A = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]

seg = segtree(A, op, e)

for q in Query:
  if q[0] == 1:
    _, x, v = q
    seg.set(x - 1 , v)
  elif q[0] == 2:
    _, l, r = q
    print(seg.prod(l - 1, r))
  elif q[0] == 3:
    _, x, v = q
    def g(n):
      return n < v
    print(seg.max_right(x - 1, g) + 1)

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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int r, D, x;
	cin >> r >> D >> x;
	int rx = x;
	for (int i = 1; i <= 10; i++)
	{
		int ans = r*rx - D;
		cout << ans << endl;
		rx = ans;

	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
  int N;
  cin>>N;
  int ans=0;
  for(int n=1;n<=N;n++){
    ans=0;
    for(int A=2;A<=141;A++){
      for(int B=2;B<=141;B++){
        if(A*A+B*B>2*n) break;
        int C=sqrt(2*n-A*A-B*B);
        int S=A+B+C;
        if(C*C==2*n-A*A-B*B && S%2==0 && S/2>max({A,B,C})){
          ans++;
        }
        
      }
    }
    cout<<ans<<endl;
    }
  return 0;}


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

int main() {
  int n; cin>>n;
  vector<char> s(n);
  rep(i, n) cin>>s[i];

  bool frag=true;
  rep(i, n/2) {
    if (s[i]!=s[n/2+i]) frag=false;
  }

  if (n%2==1) frag=false;
  if (frag) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
  return 0;
}

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

int main(void){
   string S;
   cin>>S;
   int N=S.size();
   long long ans=0;
   for(int bit=0;bit<(1<<(N-1));bit++){
      long long sum=0;
      for(int i=0;i<N-1;i++){
         sum*=10;
         sum+=(S[i]-'0');
         if(bit&((1<<i))){
            ans+=sum;
            sum=0;
         }
      }
      sum*=10;
      sum+=(S[N-1]-'0');
      ans+=sum;
   }
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<58;
const ll mod=1e9+7;


int main(){
  int i,j;
  int n;
  cin>>n;
  if(n%2==1) {
    cout<<"No"<<endl;
    return 0;
  }
  int m=n/2;
  string s;
  cin>>s;
  for(i=0;i<m;i++){
    if(s[i]!=s[i+m]) {
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  
}


Measured memory_bytes: 256
#include<stdio.h>

int sh(int i,int j,int x,int y){
	if(j<=x||y<=i){
		return j-i;
	}else if(x<=i&&j<=y){
		return (j-i)<(i-x+y-j+1)?(j-i):(i-x+y-j+1);
	}else if(j<=y){
		return (j-i)<(y-j+x-i+1)?(j-i):(y-j+x-i+1);
	}else if(x<=i){
		return (j-i)<(i-x+j-y+1)?(j-i):(i-x+j-y+1);
	}else{
		return j-i-(y-x)+1;
	}
}

int main(void){
	int n,x,y;
	scanf("%d %d %d",&n,&x,&y);
	int count[2000]={0};
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			count[sh(i,j,x,y)-1]+=1;
		}
	}
	for(int k=0;k<n-1;k++){
		printf("%d\n",count[k]);
	}
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
int A,B,C,D;
cin>>A>>B>>C>>D;
if(A+B>C+D){
    cout<<"Left";
}
else if (A+B<C+D){
    cout<<"Right";
}
else if(A+B==C+D){
    cout<<"Balanced";
}
return 0 ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) x.begin(),x.end()
#define db(x) cout<<#x<<"="<<x<<endl
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;



void Main(){

  int H,W;
  cin>>H>>W;

  rep(i,H){
    char cv[W];
    rep(j,W){
      char c;
      cin>>c;
      cv[j]=c;
    }
    rep(j,W){
      cout << cv[j];
    }
    cout<<"\n";
    rep(j,W){
      cout << cv[j];
    }
    cout<<"\n";
  }
}

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


Measured memory_bytes: 256
#include<stdio.h>

int map[22][22],N,M,ii,jj;
int xy[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
void move(int,int);
int main()
{
  int i,j,s,t;
  char ch,ch1;
  while(1){
    scanf("%d",&N);
    if(N==0)break;
    for(i=0;i<21;i++){
      for(j=0;j<21;j++){
         map[i][j]=0;
      }
    }
    ii=10;jj=10;
    for(i=0;i<N;i++){
      scanf("%d%d",&s,&t);
      map[t][s]=1;
    }
    scanf("%d",&M);
    for(i=0;i<M;i++){
      scanf("%c%c%d",&ch,&ch1,&s);
      switch(ch1){
      case 'W':
	move(0,s);
        break;
      case 'N':
        move(1,s);
	break;
      case 'E':
	move(2,s);
	break;
      default:
	move(3,s);
	break;
      }
    }
    /*map[10][10]=7;
    for(i=0;i<20;i++){
      for(j=0;j<20;j++){
        printf("%d ",map[i][j]);
      }
      printf("\n");
      }*/
    if(N==0)printf("Yes\n");
    else printf("No\n");
  }
  return 0;
}

void move(int s,int t)
{
  int i;
  for(i=0;i<t;i++){
    ii+=xy[s][0];
    jj+=xy[s][1];
    // map[ii][jj]=2;
     if(map[ii][jj]==1){
      map[ii][jj]=0;
      N--;
      }
  }
}

Measured memory_bytes: 584
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=998244353;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

double distance(ddatas& x,ddatas& y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

ll modpow(ll a,ll n){
  ll res=1;
  while(n){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}
void judgement(int a){
  if(a){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  if(a){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}

int main(){
  ll i,j,N,ans=1,cnt=1,bf=1;
  cin>>N;
  vec v(N);
  rep(i,N)cin>>v[i];
  if(v[0]){
    cout<<0<<endl;
    return 0;
  }
  vsort(v);
  if(!v[1]){
    cout<<0<<endl;
    return 0;
  }
  rep1(i,N){
    if(v[i]!=v[i-1]){
      if(v[i]-1!=v[i-1]){
        cout<<0<<endl;
        return 0;
      }
      ans=ans*modpow(bf,cnt)%mod;
      bf=cnt;
      cnt=1;
    }else{
      cnt++;
    }
  }
  ans=ans*modpow(bf,cnt)%mod;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include <cassert>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    int n, m;
    scanf(" %d %d", &n, &m);
    long long a[n], b[m][n];
    a[0] = 0;
    for (int i = 1; i < n; i++) {
        int x; scanf(" %d", &x);
        a[i] = a[i-1] + x;
    }
    for (int r = 0; r < n; r++)
        for (int t = 0; t < m; t++) scanf(" %lld", &b[t][r]);
    vector<vector<long long> > sum(n+1, vector<long long>(n+1, 0));
    for (int t = 0; t < m; t++) {
        stack<pair<int, int> > st;
        int left[n], right[n];
        st.push({1<<30, -1});
        for (int r = 0; r < n; r++) {
            while (st.top().first < b[t][r]) {
                int i = st.top().second;
                right[i] = r;
                st.pop();
            }
            left[r] = st.top().second + 1;
            st.push({b[t][r], r});
        }
        while (st.size() > 1) {
            int i = st.top().second;
            right[i] = n;
            st.pop();
        }
        for (int r = 0; r < n; r++) {
            // cerr << r << " " << left[r] << " " << right[r] << endl;
            sum[left[r]][r] += b[t][r];
            sum[r+1][r] -= b[t][r];
            if (right[r] < n) {
                sum[left[r]][right[r]] -= b[t][r];
                sum[r+1][right[r]] += b[t][r];
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (i > 0) sum[i][j] += sum[i-1][j];
            if (j > 0) sum[i][j] += sum[i][j-1];
            if (i > 0 && j > 0) sum[i][j] -= sum[i-1][j-1];
            if (j >= i) ans = max(ans, sum[i][j] - a[j] + a[i]);
        }
    printf("%lld\n", ans);

    // // check O(N^2M)
    // long long expect = 0;
    // for (int i = 0; i < n; i++) {
    //     long long mx[m];
    //     fill(mx, mx+m, 0);
    //     for (int j = i; j < n; j++) {
    //         long long sum = -(a[j] - a[i]);
    //         for (int t = 0; t < m; t++) {
    //             mx[t] = max(mx[t], b[t][j]);
    //             sum += mx[t];
    //         }
    //         expect = max(expect, sum);
    //     }
    // }
    // assert(expect == ans);
}


Measured memory_bytes: 206524
// AOJ 2200
#![allow(non_snake_case)]

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_tuple<T: std::str::FromStr + Copy>() -> (T, T) {
    let v: Vec<T> = read_vec();
    (v[0], v[1])
}

fn floyd_warshall(d: &mut Vec<Vec<i32>>) {
    let v = d.len();
    for k in 0..v {
        for i in 0..v {
            for j in 0..v {
                d[i][j] = std::cmp::min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

fn main() {
    let INF = i32::max_value() / 10;

    loop {
        let (N, M) = read_tuple::<usize>();
        if N == 0 && M == 0 {
            break;
        }

        let mut sea = vec![vec![INF; N]; N];
        let mut land = vec![vec![INF; N]; N];
        for i in 0..N {
            sea[i][i] = 0;
            land[i][i] = 0;
        }

        for i in 0..M {
            let vec: Vec<String> = read_vec();
            let x = vec[0].parse::<usize>().unwrap() - 1;
            let y = vec[1].parse::<usize>().unwrap() - 1;
            let t: i32 = vec[2].parse().unwrap();
            if vec[3].eq("S") {
                sea[x][y] = t;
                sea[y][x] = t;
            } else {
                land[x][y] = t;
                land[y][x] = t;
            }
        }

        let R: usize = read();
        let z: Vec<usize> = read_vec::<usize>().iter().map(|&i| i - 1).collect();

        floyd_warshall(&mut sea);
        floyd_warshall(&mut land);

        let mut dp = vec![INF; N];
        dp[z[0]] = 0;
        for k in 1..R {
            let mut ndp = vec![INF; N];
            for i in 0..N {
                ndp[i] = dp[i] + land[z[k-1]][z[k]];
                for j in 0..N {
                    ndp[i] = std::cmp::min(ndp[i], dp[j] + land[z[k-1]][j] + sea[j][i] + land[i][z[k]]);
                }
            }
            dp = ndp;
        }
        println!("{}", dp.iter().min().unwrap());
    }

}



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

int N, A, B;
const int MAX = 100000;
int64_t X[MAX], Y[MAX], D;
typedef tuple<int64_t, int64_t, int64_t> Tuple;
typedef pair<int64_t, int64_t> Pair;
set<Tuple> stxy, styx;
vector<Pair> vxy, vyx;
bool use[MAX];

void dfs(int i){
    if(use[i]) return;
    use[i] = true;
    vector<int> js;
    for(auto x : {X[i]-D, X[i]+D}){
        auto it = stxy.lower_bound(make_tuple(x, Y[i]-D, 0));
        while(it != stxy.end() && (*it) <= make_tuple(x, Y[i]+D, N)){
            js.push_back(get<2>(*it));
            it = stxy.erase(it);
        }
    }
    for(auto y : {Y[i]-D, Y[i]+D}){
        auto it = styx.lower_bound(make_tuple(y, X[i]-D, 0));
        while(it != styx.end() && (*it) <= make_tuple(y, X[i]+D, N)){
            js.push_back(get<2>(*it));
            it = styx.erase(it);
        }
    }
    for(auto j : js){
        if(!use[j]) dfs(j);
    }
}

int main(){
    int64_t i, j, k;
    cin >> N >> A >> B;
    A--; B--;
    for(i=0; i<N; i++){
        int64_t x, y;
        cin >> x >> y;
        X[i] = x+y;
        Y[i] = x-y;
        if(i!=A){
            stxy.insert(make_tuple(X[i], Y[i], i));
            styx.insert(make_tuple(Y[i], X[i], i));
        }
        vxy.push_back({X[i], Y[i]});
        vyx.push_back({Y[i], X[i]});
    }
    sort(vxy.begin(), vxy.end());
    sort(vyx.begin(), vyx.end());
    D = max(abs(X[A]-X[B]), abs(Y[A]-Y[B]));
    dfs(A);

    int64_t ans = 0;
    for(i=0; i<N; i++){
        if(!use[i]) continue;
        for(auto x : {X[i]-D, X[i]+D}){
            ans += upper_bound(vxy.begin(), vxy.end(), make_pair(x, Y[i]+D)) - lower_bound(vxy.begin(), vxy.end(), make_pair(x, Y[i]-D));
        }
        for(auto y : {Y[i]-D, Y[i]+D}){
            ans += lower_bound(vyx.begin(), vyx.end(), make_pair(y, X[i]+D)) - upper_bound(vyx.begin(), vyx.end(), make_pair(y, X[i]-D));
        }
    }
    cout << ans/2 << endl;
    return 0;
}

Measured memory_bytes: 26720
n = int(input())
l = []
for i in range(n):
    s,p = input().split()
    l.append([i+1,s,int(p)])
#print(l)

m = sorted(l,key=lambda x:(x[1],-x[2]))
#print(m)
for i in m:
    print(i[0])

Measured memory_bytes: 3060
#include<stdio.h>
unsigned lj[1024][32];
unsigned vis[32];
int tp[1024];
void dfs(int u,int t)
{
	if(vis[u>>5]&(1<<(u&31)))
	{
		return;
	}
	vis[u>>5]|=(1<<(u&31));
	tp[u]=t;
	for(int i=0;i<32;i++)
	{
		if((lj[u][i]&vis[i])==lj[u][i])
		{
			continue;
		}
		for(int j=0;j<32;j++)
		{
			if(lj[u][i]&(1<<j))
			{
				dfs((i<<5)+j,t);
			}
		}
	}
}
int tp2[1005][1005];
int a[262144],b[262144];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		lj[a[i]][b[i]>>5]|=(1<<(b[i]&31));
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<32;j++)
		{
			vis[j]=0;
		}
		for(int j=1;j<=n;j++)
		{
			tp[j]=0;
		}
		vis[i>>5]|=(1<<(i&31));
		for(int j=1;j<=n;j++)
		{
			if(lj[i][j>>5]&(1<<(j&31)))
			{
				dfs(j,j);
			}
		}
		for(int j=1;j<=n;j++)
		{
			if(tp[j])
			{
				tp2[i][j]=1;
			}
		}
		for(int j=1;j<=n;j++)
		{
			if(tp[j]>0&&tp[j]<j)
			{
				tp2[i][j]=2;
			}
		}
		for(int j=0;j<32;j++)
		{
			vis[j]=0;
		}
		for(int j=1;j<=n;j++)
		{
			tp[j]=0;
		}
		vis[i>>5]|=(1<<(i&31));
		for(int j=n;j>=1;j--)
		{
			if(lj[i][j>>5]&(1<<(j&31)))
			{
				dfs(j,j);
			}
		}
		for(int j=1;j<=n;j++)
		{
			if(tp[j]>j)
			{
				tp2[i][j]=2;
			}
		}
	}
	for(int i=0;i<m;i++)
	{
		if((tp2[a[i]][b[i]]>=2)^(tp2[b[i]][a[i]]>=1))
		{
			printf("diff\n");
		}
		else
		{
			printf("same\n");
		}
	}
	return 0;
}

Measured memory_bytes: 6784
#include<iostream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if(a==b)
	{
		cout<<"Draw";
		return 0;
	}
	if(a==1)
	{
		cout<<"Alice";
		return 0;
	}
	if(b==1)
	{
		cout<<"Bob";
		return 0;
	}
	if(a>b)
	{
		cout<<"Alice";
		return 0;
	}
	if(b>a)
	{
		cout<<"Bob";
		return 0;
	}
	return 0;
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

string s;

bool check(int tmp_size) {
  for (int j = 0; j < tmp_size; ++j) {
    if (s[j] != s[tmp_size + j]) return false;
  }
  return true;
}

int main(void) {
  // Here your code !
  cin >> s;

  int length = 0;

  for (int i = 2; i <= s.size(); i += 2) {
    int tmp_size = (s.size() - i) / 2;

    if (!check(tmp_size)) continue;

    length = s.size() - i;
    break;
  }

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

  return 0;
}


Measured memory_bytes: 256
import itertools

N = int(input())
S = [input() for _ in range(N)]
M, A, R, C, H = 0, 0, 0, 0, 0

for i in S:
  if i[0] == 'M':
    M += 1
  elif i[0] == 'A':
    A += 1
  elif i[0] == 'R':
    R += 1
  elif i[0] == 'C':
    C += 1
  elif i[0] == 'H':
    H += 1

comb = list(itertools.combinations([M, A, R, C, H], 3))
answer = 0 

for i in comb:
  answer += (i[0]*i[1]*i[2])

print(answer)


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

int main() {
    //入力
    int n;
    int a[2][101];
    int ans = 0;
    cin >> n;
    for (int i=0; i<2; i++) {
        for (int j=0; j<n; j++) cin >> a[i][j];
    }
    for (int i=0; i<n; i++) {
        int temp = 0;
        for (int j=0; j<=i; j++) temp += a[0][j];
        for (int j=i; j<n; j++) temp += a[1][j];
        ans = max(ans, temp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3612
def main():
    N, K = (int(i) for i in input().split())
    H = [0] + [int(i) for i in input().split()]
    if N == K:
        return print(0)
    elif K == 0:
        ans = 0
        for i in range(N):
            ans += max(H[i+1] - H[i], 0)
        return print(ans)

    dp = [[10**10]*(N-K+1) for i in range(N+1)]
    dp[0][0] = 0
    for i, h in enumerate(H):
        if i == 0:
            continue
        dp[i][1] = h
    for i in range(1, N+1):
        for j in range(1, N-K+1):
            for x in range(1, i):
                dp[i][j] = min(dp[i][j], dp[x][j-1] + max(0, H[i] - H[x]))
    ans = 10**10
    for i in range(N+1):
        # print(dp[i])
        ans = min(ans, dp[i][N-K])
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 42460
#include<bits/stdc++.h>
#define max(a,b) (((a)>(b))?a:b)
#define min(a,b) (((a)<(b))?a:b)
using namespace std;
template<typename T>void read(T &x){
	x=0;int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if (c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-48;
	x*=f;
}
char s[100010];
int fa[100010];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	if(s[1]=='0'||s[n]=='1') {puts("-1");return 0;}
	for(int i=1;i<=n-1;++i)
		if(s[i]!=s[n-i]) {puts("-1");return 0;}
	int lcc=1,nown=1;
	for(int i=2;i<=n-1;++i)
		if(s[i]=='1') {
			nown=i;
			for(int j=lcc;j<=nown-1;++j)
				fa[j]=nown;
			lcc=i;
		}
	nown=n;
	for(int i=lcc;i<=nown-1;++i)
		fa[i]=nown;
	for(int i=1;i<=n-1;++i)
		printf("%d %d\n",i,fa[i]);
	return 0;
}


Measured memory_bytes: 1920
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
     String[] nyu=sc.nextLine().split(" ");

   //  String nyu=sc.nextLine();
int A=Integer.parseInt(nyu[0]);
int B=Integer.parseInt(nyu[1]);
int C=Integer.parseInt(nyu[2]);
int D=Integer.parseInt(nyu[3]);



//double A=Double.parseDouble(nyu[0]);
//double B=Double.parseDouble(nyu[1]);
/*
switch(C){
case 7:
case 5:
case 3:
System.out.println("YES") ;
break;
default:
System.out.println("NO") ;

break;
}
*/

//int res=(24-C)+24;
if(A+B<C+D){

System.out.println("Right");
}else if(A+B>C+D){
System.out.println("Left");

}else{
System.out.println("Balanced");

}




	}
}

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

vector<vector<int> > A;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  A.assign(N, vector<int>());
  for(int i = 1; i < N; i++){
    int tmp; cin >> tmp; tmp--;
    A[tmp].push_back(i);
  }
  REP(i, N){
    cout << A[i].size() << endl;
  }
}

Measured memory_bytes: 14284
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	double x,y,z;
};

double calc_len(Info a,Info b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}


void func(){

	double QR,RP,PQ;
	scanf("%lf %lf %lf",&QR,&RP,&PQ);

	int num_points;
	scanf("%d",&num_points);

	Info info[num_points+1];

	for(int i = 1; i <= num_points; i++){
		scanf("%lf %lf %lf",&info[i].x,&info[i].y,&info[i].z);
	}

	int ans_Q,ans_R,ans_P;
	bool FLG = false;

	double tmp_QR,tmp_RP,tmp_PQ;
	double ratio_QR,ratio_RP,ratio_PQ;

	for(int Q = 1; Q <= num_points; Q++){
		for(int R = 1; R <= num_points; R++){
			if(Q == R)continue;
			for(int P = 1; P <= num_points; P++){
				if(Q == P || R == P)continue;

				tmp_QR = calc_len(info[Q],info[R]);
				tmp_RP = calc_len(info[R],info[P]);
				tmp_PQ = calc_len(info[P],info[Q]);

				ratio_QR = tmp_QR/QR;
				ratio_RP = tmp_RP/RP;
				ratio_PQ = tmp_PQ/PQ;

				if(fabs(ratio_QR-ratio_RP) < 0.1 && fabs(ratio_QR-ratio_PQ) < 0.1 && fabs(ratio_RP-ratio_PQ) < 0.1){
					ans_Q = Q;
					ans_R = R;
					ans_P = P;

					FLG = true;
					break;
				}
			}
			if(FLG)break;
		}
		if(FLG)break;
	}

	printf("%d %d %d\n",ans_P,ans_Q,ans_R);
}


int main(){

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

	for(int i = 0; i < N; i++)func();

	return 0;
}

Measured memory_bytes: 3176
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	a, b = input().split()
	v,w = IN()
	ss=input()
	if ss == a:
		v=v-1
	else:
		w=w-1
		
	print(str(v)+' '+str(w))
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 38324
#include <string>
#include <iostream>
#include <vector>

using namespace std;

vector<char> s;

int main() {
    int N;
    string S;
    cin >> N >> S;
    for (int i = 0; i < N; ++i) {
        if(s.empty() ||  s.back() != S[i]) {
            s.push_back(S[i]);
        }
    }
    cout << s.size() << endl;
}

Measured memory_bytes: 640
import sys

a, b, k = map(int, sys.stdin.readline().split())
m = min(a, b) + 1
anslist = []
cnt = 0
for i in range(1, m):
    if a % i == 0 and b % i == 0:
        anslist.append(i)
anslist.reverse()
print(anslist[k-1])


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

int main() {
   int A,B,C,D,E;
  cin >>A>>B>>C>>D>>E;
  int a=A%10,b=B%10,c=C%10,d=D%10,e=E%10;
  vector<int> g ={a,b,c,d,e};
  sort(g.begin(),g.end());
  int goukei=A+B+C+D+E-a-b-c-d-e+50;
  for(int i = 0;i<g.size();i++){
    if(g.at(i)==0){
      goukei-=10;
    }
    else {goukei+=g.at(i)-10;
break;
  }
  }
  cout << goukei << endl;
}

Measured memory_bytes: 256
// kyopro.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include<map>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<vector>
#include<string>
using namespace std;
#define ll long long int
#define rep(N) for(ll i=0;i<N;i++)
#define For(i,N) for(ll i=0;i<N;i++)
int main()
{
    ll r;
    cin >> r;
    cout << 3 * r * r;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	int a,b;

	setvbuf(stdout,NULL,_IONBF,0);
	scanf("%d %d",&a,&b);
	fflush(0);

	if(6<=a&&a<=12){
			printf("%d",b/2);
	}else if(a<=5){
		printf("%d",0);
	}else{
		printf("%d",b);
	}
	return 0;
}

Measured memory_bytes: 128
import * as fs from 'fs';
 
const lines = fs.readFileSync('/dev/stdin', 'utf8').split("\n");
let [n,k] = lines[0].split(" ").map(Number);
let h = lines[1].split(" ").map(Number);
h.sort((a, b)=>b-a);
let ans = 0;
for(let i = k; i < n; i++){
    ans += h[i];
}
console.log(ans);

Measured memory_bytes: 34588
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N,thou,hund,ten,one;
  cin >> N;
  
  one = N % 10;
  ten = ( N % 100 - N % 10 ) / 10;
  hund = ( N % 1000 - N % 100 ) / 100;
  thou = ( N - N % 1000 ) / 1000;
  
  if (one == ten && ten == hund){
    cout << "Yes" << endl;
  }
  
  else if ( ten == hund && hund == thou){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,a,min = 1001, max = -1;
    cin >> n;
    for(int i=1; i <= n; i++){
        cin >> a;
        if(min > a) min = a;
        if(max < a) max = a;
    }
    cout << max - min << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int kaijou(int i){
  int n = 1;
  for(int j = 0; i > j; j++){
    n *= 10;
  }
  return n;
}
int kakukai(int i){
  int r = 1;
  int i_2 = i;
  int kai = 0;
  int kaku = 0;
  while(i_2 / 10){
    kai++;
    i_2 = i_2/10;
  }
  int rr = 0;
  int tmp2 = 0;
  for(int j = kai; 0 <= j; j--){
    kaku += (i / kaijou(j)) - tmp2 * 10;
    tmp2 = (i / kaijou(j));
    rr++;
  }
  return kaku;
}

int main(){
  int N;
  cin >> N;
  
  int waru = 1;
  waru = kakukai(N);
  if(N % waru == 0){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

struct PrimalDual{
  const int INF = 1<<28;
  typedef pair<int,int> P;
  struct edge{
    int to,cap,cost,rev;
    edge(){}
    edge(int to,int cap,int cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
  };

  int n;
  vector<vector<edge> > G;
  vector<int> h,dist,prevv,preve;

  PrimalDual(){}
  PrimalDual(int sz):n(sz),G(sz),h(sz),dist(sz),prevv(sz),preve(sz){}
  
  void add_edge(int from,int to,int cap,int cost){
    G[from].push_back(edge(to,cap,cost,G[to].size()));
    G[to].push_back(edge(from,0,-cost,G[from].size()-1));
  }

  int flow(int s,int t,int f){
    int res=0;
    fill(h.begin(),h.end(),0);
    while(f>0){
      priority_queue<P,vector<P>,greater<P> > que;
      fill(dist.begin(),dist.end(),INF);
      dist[s]=0;
      que.push(P(0,s));
      while(!que.empty()){
        P p=que.top();que.pop();
        int v=p.second;
        if(dist[v]<p.first) continue;
        for(int i=0;i<(int)G[v].size();i++){
          edge &e=G[v][i];
          if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
            dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
            prevv[e.to]=v;
            preve[e.to]=i;
            que.push(P(dist[e.to],e.to));
          }
        }
      }
      if(dist[t]==INF) return -1;
      for(int v=0;v<n;v++) h[v]+=dist[v];
      int d=f;
      for(int v=t;v!=s;v=prevv[v]){
        d=min(d,G[prevv[v]][preve[v]].cap);
      }
      f-=d;
      res+=d*h[t];
      for(int v=t;v!=s;v=prevv[v]){
        edge &e=G[prevv[v]][preve[v]];
        e.cap-=d;
        G[v][e.rev].cap+=d;
      }
    }
    return res;
  }
};

int main(){
  int v,e,f;
  cin>>v>>e>>f;
  PrimalDual pd(v);
  for(int i=0;i<e;i++){
    int u,v,c,d;
    cin>>u>>v>>c>>d;
    pd.add_edge(u,v,c,d);
  }
  cout<<pd.flow(0,v-1,f)<<endl;
  return 0;
}


Measured memory_bytes: 3164