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

using namespace std;

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

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

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

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

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

template<typename T>
struct SparseTable {
    int n;
    int m;
    vector<vector<T>> minA;

    void init(const vector<T>& A) {
        n = A.size();
        if (n == 0)
            return;
        m = floor(log2(n)) + 1;

        minA.resize(m);
        for (int i = 0; i < m; i++)
            minA[i].resize(n);
        copy(A.begin(), A.end(), minA[0].begin());

        for (int i = 1; i < m; i++) {
            for (int j = 0; j + (1<<i) <= n; j++) {
                minA[i][j] = min(minA[i-1][j], minA[i-1][j+(1<<(i-1))]);
            }
        }
    }

    T query_minimum_value(int x, int y) {
        int len = (y - x + 1);
        int m = floor(log2(len));
        return min(minA[m][x], minA[m][y-(1<<m)+1]);
    }

    void dump() {
        for (int i = 0; i < minA.size(); i++)
            cout << "minA[" << i << "]: " << minA[i] << endl;
    }
};

SparseTable<int> sparse;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    vector<int> A;
    int ans = 0;
    cin >> n;
    A.resize(n);
    for (int i = 0; i < n; i++)
        cin >> A[i];
    sparse.init(A);
    for (int i = 0; i < n; i++) {
        if (sparse.query_minimum_value(0, i) >= A[i]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int n, m;
vector<int> et[8];

int dfs(int v, int used) {
	used |= (1 << v);
	if (used == (1 << n) - 1) return 1;
	int ret = 0;
	for (int i = 0; i < et[v].size(); i++) {
		int nv = et[v][i];
		if ((used >> nv) & 1) continue;
		ret += dfs(nv, used + (1 << nv));
	}
	return ret;
}

int main() {
	int i;
	
	cin >> n >> m;
	for (i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		et[a].push_back(b);
		et[b].push_back(a);
	}
	
	cout << dfs(0, 0) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INF 3000
#define INFF 9223372036854775807
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "debug" << endl;
#define push_back pb
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() {
    cin.tie(0);    
	ios::sync_with_stdio(false);
    int H,W;
    cin >> H >> W;
    char A[1010][1010];
    for(int i = 1; i <= H; i++){  //後々のために1-indexにする
        for(int j = 1; j <= W; j++){
            cin >> A[i][j];
        }
    }
    int D[1010][1010] = {};
    int ans = 0;
    for(int i = 0; i < 1002; i++){
        //盤外にINFを代入して、範囲外の参照に対処する
        D[0][i] = D[i][0] = D[H+1][i] = D[i][W+1] = INF;
    }
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            if(A[i][j] == '#'){  //#スタートだから０を代入
                D[i][j] = 0;
            }
            else{  //最小の値＋１がそのマスの最短の値となる
                D[i][j] = min(D[i-1][j],D[i][j-1]) +1;
            }
        }
    }
    for(int i = H; i > 0; i--){
        for(int j = W; j > 0;j--){
            //上のfor文で左上から＃の最短距離を数えたのに対し
            //ここのfor文では右下から＃の最短距離を数える（天才の発想）
            //対極から二度数えることでそれぞれの撃墜ケースをなくす
            //また二度目のfor文では一度目のfor文との比較も行う。
            D[i][j] = min({D[i][j],D[i+1][j]+1,D[i][j+1]+1});
        }
    }
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            ans = max(ans,D[i][j]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 5248
# -*- coding: utf-8 -*-
"""
Created on Tue Mar 17 00:21:01 2020

@author: Kanaru Sato
"""

import itertools as it
n = int(input())

p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

L = list(it.permutations(range(1,n+1)))

a = L.index(p)
b = L.index(q)
print(abs(a-b))

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

#define ll long long

using namespace std;

int main() {
  ll N, K;
  cin >> N >> K;
  vector<ll> H(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }
  sort(H.begin(), H.end(), greater<ll>());
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    if (K > 0) {
      K--;
    } else {
      ans += H[i];
    }
  }
  cout << ans << endl;
}


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

constexpr int MAX_N = 1e5;

int sum[MAX_N+1];

int main() {
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;

  sum[0] = 0.0;
  for (int i{}; i < N; ++i) {
    double val = i < N-1 && S[i] == 'A' && S[i+1] == 'C' ? 1 : 0;
    sum[i+1] = sum[i] + val;
  }

  for (int i{}; i < Q; ++i) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    cout << sum[r] - sum[l] << endl;
  }

  return 0;
}


Measured memory_bytes: 1408
type t = { v : int; w : int }

let solve a n w =
  let s = Array.make (w + 1) 0 in
  let t = Array.copy s in
  for i = 1 to n do
    for j = a.(i-1).w to w do
      t.(j) <-
        if s.(j) >= s.(j - a.(i-1).w) + a.(i-1).v
        then s.(j)
        else s.(j - a.(i-1).w) + a.(i-1).v;
    done;
    Array.iteri (fun i e -> s.(i) <- e) t;
  done;
  t.(w)

let () =
  let (n, w) = Scanf.scanf "%d %d " (fun n w -> n, w) in
  let a = Array.init n (fun _ -> Scanf.scanf "%d %d " (fun v w -> { v; w })) in
  solve a n w |> Printf.printf "%d\n"

Measured memory_bytes: 2596
#include <cstring>
#include <iostream>
using namespace std;

const int N_MAX = 1 << 15;
int results[N_MAX];

int main () {
	memset(results, 0, sizeof(results));
	for (int i = 0; i * i < N_MAX; i++) {
		for (int j = 0; j <= i && i * i + j * j < N_MAX; j++) {
			for (int k = 0; k <= j && i * i + j * j + k * k < N_MAX; k++) {
				for (int l = 0; l <= k && i * i + j * j + k * k + l * l < N_MAX; l++) {
					results[i * i + j * j + k * k + l * l]++;
				}
			}
		}
	}
	int n;
	while (cin >> n, n) {
		cout << results[n] << endl;
	}
	return 0;
}

Measured memory_bytes: 1296
import math
a, b, h, m = map(int, input().split())

rh = h*30 + m*0.5
rm = m*6
angleC = math.radians(abs(rh - rm))
if angleC > math.pi:
    angleC = math.pi*2 - angleC

c = a**2 + b**2 - 2*a*b * math.cos(angleC)
print(math.sqrt(c))


Measured memory_bytes: 9380
#include <bits/stdc++.h>
using namespace std;
 
#define N (int)1e3+5
#define f1 first
#define s2 second
#define INF 9999999
#define pb push_back
#define ll long long
#define mod (int)1e9+7
#define ull unsigned long long;
#define all(a) a.begin(),a.end()
#define fri(a) freopen(a,"r",stdin);
#define fro(a) freopen(a,"w",stdout);

int n;
string str;

int main(){
	//fri("in.txt");
	//fro("out.txt");
	cin>>n>>str;
	for(int i=0;i<str.length();i++){
		str[i]+=n;
		//str[i]%=65;
		str[i]-=str[i]>90?26:0;
	}
	cout<<str<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	int i,n;cin>>n;
	int ans=0,A=0,B=0,kata=0;
	for(i=0;i<n;i++){
		string str;cin>>str;
		for(int j=0;j+1<str.size();j++){
			if(str[j]=='A'&&str[j+1]=='B'){ans++;}
		}
		if(str.back()=='A'){A++;}
		if(str[0]=='B'){B++;}
		if((str.back()=='A')!=(str[0]=='B')){kata=1;}
	}
	cout<<ans+max(0,min(A,B)-1+kata)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cout << #x << '=' << x << '\n'
const long long MOD=1e9+7;
//const long long MOD=998244353;
const int INF=1e9;
const long long IINF=1e18;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
const char dir[4]={'D','R','U','L'};

template<typename T>
istream &operator>>(istream &is,vector<T> &v){
    for (T &x:v) is >> x;
    return is;
}
template<typename T>
ostream &operator<<(ostream &os,const vector<T> &v){
    for (int i=0;i<v.size();++i){
        os << v[i] << (i+1==v.size()?"": " ");
    }
    return os;
}
template<typename T,typename U>
ostream &operator<<(ostream &os,const pair<T,U> &p){
    cout << '(' << p.first << ',' << p.second << ')';
    return os;
}

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

vector<ll> po(19,1);

ll calc(int i,int j,ll e){
    if (j>i-1-j) return (e==0?1:0);
    ll res=0;
    ll diff=(j==i-1-j?0:e/(po[i-1-j]-po[j]));
    for (ll d=diff-1;d<=diff+1;++d){
        if (j==i-1-j&&d!=0) continue;
        ll ne=e-(po[i-1-j]-po[j])*d;
        if (ne<-(po[i-1-j]-po[j])||po[i-1-j]-po[j]<ne) continue;
        for (int k=(!j?1:0),cnt=0;k<10;++k){
            if (k+d>=0&&k+d<10) ++cnt;
            if (k==9) res+=calc(i,j+1,ne)*cnt;
        }
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i=0;i<18;++i) po[i+1]=po[i]*10;
    ll D; cin >> D;
    ll ans=0;
    for (int i=2;i<=19;++i){
        ans+=calc(i,0,D);
    }
    cout << ans << '\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) a[i]--;
    vector<int> s(n + 1);
    rep(i, n) {
        s[i+1] = (s[i] + a[i]) % k;
    }

    map<int, int> mp;
    ll ans = 0;
    queue<int> q;
    rep(j, n + 1) {
        ans += mp[s[j]];
        mp[s[j]]++;
        q.push(s[j]);
        while (q.size() >= k) {
            mp[q.front()]--;
            q.pop();
        }
    }

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

Measured memory_bytes: 12032
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const int inf = (int) 1e9;

int main() {
  int n;
  cin >> n;
  int arr[n];
  long long dp[n];
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  dp[0] = 0;
  for (int i = 1; i < n; i++) {
    dp[i] = inf;
    dp[i] = min(dp[i], dp[i - 1] + abs(arr[i - 1] - arr[i]));
    if (i >= 2) {
      dp[i] = min(dp[i], dp[i - 2] + abs(arr[i - 2] - arr[i]));
    }
  }
  cout << dp[n - 1] << endl;
  return 0;
}


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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  while (1) {
    C -= B;
    if (C <= 0) return cout << "Yes" << "\n", 0;
    A -= D;
    if (A <= 0) return cout << "No" << "\n", 0;
  }
}

Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}


int main(){
    int n;
    cin >>n;
    vector<ll> a(n),b(n);
    REP(i,n){
        cin >> a[i];
    }
    REP(i,n){
        cin >> b[i];
    }
    ll c = 0;
    REP(i,n){
        ll t = b[i]-a[i];
        if(t<0){
            c+=t;
        }else{
            c+=t/2;
        }
        //c += min(t,t*2);
    }
    if(c>=0){
        put("Yes");
    }else{
        put("No");
    }
    return 0;
}


Measured memory_bytes: 384
def hikaku(n1, n2):
    for x, y in zip(n1, n2):
        if ord(x) == ord(y):
            continue
        else:
            return True if ord(x) > ord(y) else False
num, length = map(int, input().split())
wlist = []
for i in range(num):
    wlist.append(input())
for n in range(num - 1):
    kumi = [(x, x+1) for x in range(num - 1 - n)]
    if kumi:
        for x, y in kumi:
            if hikaku(wlist[x], wlist[y]):
                wlist[x], wlist[y] = wlist[y], wlist[x]
dst = ""
for w in wlist:
    dst += w
print(dst)


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

long long a(long long i){
  if(i == 1) return 1;
  else{
    return 2 * a(i / 2) + 1;
  }
}

int main(){
  long long h;
  cin >> h;
  cout << a(h) << endl;
}

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

def main():
    N, x = map(int, input().split())
    a = list(map(int, input().split()))

    min_ = np.array(a)

    ans = sum(min_)
    # 魔法を唱える回数 k
    for k in range(1, N):
        min_ = np.minimum(min_, np.roll(min_, 1))
        ans = min(ans, k * x + sum(min_))
    print(ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 14260
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N)]
CD = [tuple(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
CD.sort(key=lambda x: x[0])
ans = 0
for c,d in CD:
    idx = 10000
    for i in range(N):
        if AB[i] == -1:
            continue
        if c < AB[i][0]:
            break
        if AB[i][1] < d:
            if idx == 10000:
                idx = i
            elif AB[idx][1] < AB[i][1]:
                idx = i
    if idx != 10000:
        ans += 1
        AB[idx] = -1
print(ans)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
def main():
    L,R = map(int,input().split())
    LR = R-L
    M = []
    if L <= 2019 <= R:
        print(0)
        exit()
    for i in range(LR):
        for j in range(LR):
            M.append(((L+i)*(L+1+j))%2019)
            if ((L+i)*(L+1+j))%2019 == 0:
                print(0)
                exit()
    print(min(M))
if __name__ == '__main__':
    main()

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

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}






int gcd(int a,int b)
{
 
  int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int h,w;
  cin>>h>>w;
  vector<string> v(h);
  rep(i,h) cin>>v[i];
  rep(i,w+2) cout<<'#';
  cout<<endl;
  rep(i,h){
    cout<<'#'<<v[i]<<'#'<<endl;
  }
  rep(i,w+2) cout<<'#';
  cout<<endl;
}
///////////////////////////



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

int main(){
  int x,y;
  cin >> x >> y;
  if(x==2||y==2){
    cout << "No" << endl;
  }
  else if(x==1&&y==3){
    cout << "Yes" << endl;
  }
  else if(x==1&&y==5){
    cout << "Yes" << endl;
  }
  else if(x==1&&y==7){
    cout << "Yes" << endl;
  }
  else if(x==1&&y==8){
    cout << "Yes" << endl;
  }
  else if(x==1&&y==10){
    cout << "Yes" << endl;
  }
  else if(x==1&&y==12){
    cout << "Yes" << endl;
  }
  else if(x==3&&y==5){
    cout << "Yes" << endl;
  }
  else if(x==3&&y==7){
    cout << "Yes" << endl;
  }
  else if(x==3&&y==8){
    cout << "Yes" << endl;
  }
  else if(x==3&&y==10){
    cout << "Yes" << endl;
  }
  else if(x==3&&y==12){
    cout << "Yes" << endl;
  }
  else if(x==5&&y==7){
    cout << "Yes" << endl;
  }
  else if(x==5&&y==8){
    cout << "Yes" << endl;
  }
  else if(x==5&&y==10){
    cout << "Yes" << endl;
  }
  else if(x==5&&y==12){
    cout << "Yes" << endl;
  }
  else if(x==7&&y==8){
    cout << "Yes" << endl;
  }
  else if(x==7&&y==10){
    cout << "Yes" << endl;
  }
  else if(x==7&&y==12){
    cout << "Yes" << endl;
  }
  else if(x==8&&y==10){
    cout << "Yes" << endl;
  }
  else if(x==8&&y==12){
    cout << "Yes" << endl;
  }
  else if(x==10&&y==12){
    cout << "Yes" << endl;
  }
  else if(x==4&&y==6){
    cout << "Yes" << endl;
  }
  else if(x==4&&y==9){
    cout << "Yes" << endl;
  }
  else if(x==4&&y==11){
    cout << "Yes" << endl;
  }
  else if(x==6&&y==9){
    cout << "Yes" << endl;
  }
  else if(x==6&&y==11){
    cout << "Yes" << endl;
  }
  else if(x==9&&y==11){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <iterator>
#include <string>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
//i64 mod = 1000000007;
//int int_max = 2147483647;
i64 INF = 1e12;
int max_n = 1e5;

template<typename IntType>
struct mat2d_t {
    mat2d_t(size_t h, size_t w) : h(h), w(w) {
        mat = std::vector<std::vector<IntType>>(h, std::vector<IntType>(w, 0));
    }
    mat2d_t(size_t h, size_t w, IntType init) : h(h), w(w){
        mat = std::vector<std::vector<IntType>>(h, std::vector<IntType>(w, init));
    }

    std::vector<IntType>& operator[](size_t p) {
        return mat[p];
    }

    const std::vector<IntType>& operator[](size_t p) const {
        return mat[p];
    }
    size_t height() const {
        return h;
    }
    size_t width() const {
        return w;
    }

private:
    std::vector<std::vector<IntType>> mat;
    size_t h;
    size_t w;
};

int main(int argc, char **argv) {
    i64 n,w;
    cin >> n >> w;

    vector<i64> weight(n+1);
    vector<i64> cost(n+1);
    for (int i=1; i<n+1; ++i) {
        cin >> weight[i] >> cost[i];
    }
    mat2d_t<i64> dp(n+1, w+1, 0);
    dp[0][0] = 0;
    for (int i=1; i<n+1; ++i) {
        i64 w_i = weight[i];
        i64 v_i = cost[i];

        for (int j=0; j<w+1; ++j) {
            if (j-w_i >= 0 && j-w_i <= w) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout << dp[n][w] << endl;
    return 0;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int n;
long double p[3030];
long double dp[3300][3300];//i番目までにj個表
int main(){cout<<fixed<<setprecision(10);
		   cin>>n;
           rep(i,1,n+1)cin>>p[i];
           dp[0][0]=1;
           rep(i,1,n+1){
            rep(j,0,n+1){
             dp[i][j]=dp[i-1][j]*(1-p[i]);
             if(j-1>=0)dp[i][j]+=dp[i-1][j-1]*p[i];
            }
           }
           long double ans=0;
           rep(j,n/2+1,n+1){
             ans+=dp[n][j];
           }
             cout<<ans<<endl;
}

Measured memory_bytes: 156380
#

array = list(map(int, input().strip().split(' ')))


N =  array[0]

T =  array[1]


#print(N)
#print(T)

if N < 1:
    sys.exit()

if N > 100:
    sys.exit()


if T < 1:
    sys.exit()

if T > 1000:
    sys.exit()



c_min = 9999


for i in range(N):
    array1 = list(map(int, input().strip().split(' ')))
    cN =  array1[0]

    tN =  array1[1]

    if cN < 1:
        sys.exit()

    if cN > 1000:
        sys.exit()

    if tN < 1:
        sys.exit()

    if tN > 1000:
        sys.exit()
    
    if tN <= T:
        if c_min > cN:

            c_min = cN

if c_min == 9999:
    print("TLE")

else:
    print(c_min)

    


Measured memory_bytes: 3064
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<map>
#include<cstring>

using namespace std;

int main()
{
	int x, n;

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

	int a[101] = { 0, };

	for (int i = 0; i < n; i++)
	{
		int input;

		scanf("%d", &input);

		a[input] = 1;
	}

	if (!a[x])
	{
		printf("%d\n", x);

		return 0;
	}

	for (int i = 1; i <= 101; i++)
	{
		if (x - i <= 0 || !a[x - i])
		{
			printf("%d\n", x - i);

			return 0;
		}

		if (x + i > 100 || !a[x + i])
		{
			printf("%d\n", x + i);

			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 1736
// https://atcoder.jp/contests/abc107/tasks/arc101_a

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

// int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
    int n, k, ans = INF;
    vector<int> x;
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    x.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    sort(ALL(x));

    // k本のロウソクに火をつける時間を計算
    for (int i = 0; i <= n - k; i++) {
        // 比較対象の符号が逆の場合
        int a = x[i], b = x[i + k - 1];
        if (signbit(a) != 0 && signbit(b) == 0 ||
            signbit(a) == 0 && signbit(b) != 0) {
            if (abs(a) < abs(b)) {
                ans = min(ans, 2 * abs(a) + abs(b));
            } else {
                ans = min(ans, abs(a) + 2 * abs(b));
            }
        } else {
            ans = min(ans, max(abs(a), abs(b)));
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 768
n = int(input())
s = input()
flag = True
if n % 2 == 1:
    flag = False
for i in range(0,n // 2):
    if s[i] != s[int(i + (n // 2))]:
        flag = False
        break
if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
s = int(input())
intlist = list()
intlist.append(s)
i = 0
end = True
while end:
    s2 = 0
    if intlist[i] % 2 == 0:
        s2 = intlist[i] / 2
    else:
        s2 = 3 * intlist[i] + 1
    i += 1
    for j in intlist:
        if s2 == j:
            print(i + 1)
            end = False
            break
    intlist.append(s2)

Measured memory_bytes: 3060
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n;
    cin>>n;
    ll a[n+1],prefix[n+1];;
    a[0]=0,prefix[0]=0;
    for(int i=1;i<n+1;++i) cin>>a[i],prefix[i]=prefix[i-1]+a[i];
    ll dp[n+1][n+1];
    for(int i=0;i<n+1;++i) dp[i][i] = 0;
    for(int i=1;i<n;++i) dp[i][i+1] = a[i]+a[i+1];
    for(int i=2;i<n;++i){
        for(int j=1;j+i<n+1;++j){
            dp[j][j+i] = LONG_MAX;
            for(int k=j;k<j+i;++k){
                dp[j][j+i] = min(dp[j][j+i],dp[j][k]+dp[k+1][j+i]+prefix[j+i]-prefix[j-1]);
            }
        }
    }
    cout<<dp[1][n];
}

Measured memory_bytes: 4836
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll h=0,ans=0,mult=1;
	cin>>h;
	while(h!=0){
		ans+=mult;
		mult*=2;
		h/=2;
	}
	puta(ans);
	
}


Measured memory_bytes: 256
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	var X int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d", &X)

	for X > 1 {
		facts := make(map[int]int)
		factoring(X, facts)
		g := -1
		for _, pow := range facts {
			if g < 0 {
				g = pow
			} else {
				g = gcd(g, pow)
			}
		}
		if g >= 2 {
			break
		}
		X--
	}
	fmt.Println(X)
}

func factoring(n int, facts map[int]int) {
	for i := 2; i*i <= n; i++ {
		for n%i == 0 {
			facts[i]++
			n = n / i
		}
	}
	if n != 1 {
		facts[n]++
	}
}

func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		tmp := a % b
		a, b = b, tmp
	}
	return a
}


Measured memory_bytes: 640
integer N
integer,allocatable,dimension(:)::V,V1,V2
integer V1no1,V2no1,V1no1cnt,V1no2cnt,V2no1cnt,V2no2cnt,tmp,tmpcnt
read*,N
allocate(V(N),V1(N/2),V2(N/2))
read*,V
do i=1,N
  if(mod(i,2)==1)then
    V1(i/2+1)=V(i)
  else
    V2(i/2)=V(i)
  endif
end do
call Heapsort(N/2,V1)
call Heapsort(N/2,V2)
V1no1=V1(1);V1no2=0;V1no1cnt=0;V1no2cnt=0;tmp=0;tmpcnt=0
do i=1,N/2
  if(V1(i)==tmp)then
    tmpcnt=tmpcnt+1
  else
    if(V1no1cnt<tmpcnt)then
       V1no1=tmp
       V1no2cnt=V1no1cnt;V1no1cnt=tmpcnt
     else if(V1no2cnt<tmpcnt)then
       V1no2cnt=tmpcnt
     endif
     tmp=V1(i);tmpcnt=1
  endif
end do
if(V1no1cnt<tmpcnt)then
  V1no1=tmp
  V1no2cnt=V1no1cnt;V1no1cnt=tmpcnt
else if(V1no2cnt<tmpcnt)then
  V1no2cnt=tmpcnt
endif

V2no1=V2(1);V2no2=0;V2no1cnt=0;V2no2cnt=0;tmp=0;tmpcnt=0
do i=1,N/2
  if(V2(i)==tmp)then
    tmpcnt=tmpcnt+1
  else
    if(V2no1cnt<tmpcnt)then
       V2no1=tmp
       V2no2cnt=V2no1cnt;V2no1cnt=tmpcnt
     else if(V2no2cnt<tmpcnt)then
       V2no2cnt=tmpcnt
     endif
     tmp=V2(i);tmpcnt=1
  endif
end do
if(V2no1cnt<tmpcnt)then
  V2no2=V2no1;V2no1=tmp
  V2no2cnt=V2no1cnt;V2no1cnt=tmpcnt
else if(V2no2cnt<tmpcnt)then
  V2no2cnt=tmpcnt
endif
if(V1no1/=V2no1)then
  print"(i0)",N-V1no1cnt-V2no1cnt
else
  print"(i0)",min(N-V1no1cnt-V2no2cnt,N-V1no2cnt-V2no1cnt)
endif
contains
subroutine heapsort(n,array)
  implicit none
!ここの入力は状況に応じて変更すること
  integer,intent(in) :: n
  integer,intent(inout) :: array(1:n)
  integer::i,k,j,l
  integer:: t

  l=n/2+1
  k=n
  do while(k /= 1)
     if(l > 1)then
        l=l-1
        t=array(L)
     else
        t=array(k)
        array(k)=array(1)
        k=k-1
        if(k == 1) then
           array(1)=t
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j<=k)
        if(j < k)then
           if(array(j) < array(j+1))j=j+1
        endif
        if (t < array(j))then
           array(i)=array(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     enddo
     array(i)=t
  enddo
  return
end subroutine heapsort
end

Measured memory_bytes: 1536
import collections
N = int(input())
l = []
for i in range(N):
  s = input()
  ls = []
  for j in range(10):
    ls.append(s[j])
  ls.sort()
  sm = ""
  for j in range(10):
    sm += ls[j]
  l.append(sm)

cnt = 0
c = collections.Counter(l)
for i in c.values():
  cnt += i*(i-1)//2
print(cnt)        

Measured memory_bytes: 19824
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

#define gsort(b, e) sort(b, e, greater<decltype(*b)>())

template <typename T>
T sq(T a) {
    return a * a;
}

int main() {
    double x[3], y[3];
    for (int i = 0; i < 3; ++i) {
        cin >> x[i] >> y[i];
    }

    // (x[0], y[0])を原点に平行移動
    for (int i = 2; i >= 0; --i) {
        x[i] -= x[0];
        y[i] -= y[0];
    }

    // 三角形の面積
    double S = abs(x[1] * y[2] - x[2] * y[1]) / 2;

    // 各辺の長さ
    double r[3];
    for (int i = 0; i < 3; ++i) {
        r[i] = sqrt(sq(x[i] - x[(i + 1) % 3]) + sq(y[i] - y[(i + 1) % 3]));
    }

    // 内接円の半径
    double z = S * 2 / (r[0] + r[1] + r[2]);
    gsort(r, r + 3);

    double ok = 0, ng = 1000;
    for (int i = 0; i < 100; ++i) {
        double mid = (ok + ng) / 2;
        if (mid * 2 <= r[0] * (1 - mid / z)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    cout << fixed << setprecision(15) << ok << endl;
    return 0;
}


Measured memory_bytes: 256
//https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_A

#include <bits/stdc++.h>

using namespace std;

int coin_change(const int coins[], int cn, int money) {
    int table[money + 1];
    table[0] = 0;

    int pred[money + 1];
    for (int i = 0; i <= money; i++) {
        pred[i] = 0;
    }

    for (int j = 1; j <= money; j++) {
        table[j] = INT_MAX;
    }

    for (int i = 1; i <= money; i++) {
        int mini = table[i];
        for (int j = 0; j < cn; j++) {
            if (i >= coins[j]) {
                mini = min(mini, table[i - coins[j]] + 1);
                pred[i] = j;
            }
        }
        table[i] = mini;
    }

    return table[money];
}


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

    int coins[m];
    for (int i = 0; i < m; ++i) {
        cin >> coins[i];
    }

    cout << coin_change(coins, m, n) << endl;
    return 0;
}

/*
 * spaghetti-sourceのコードを利用。
 *
 */


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

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF ((1LL<<62)-1)
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME ((1ll<<61)-1)

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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

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

template<class T>
inline void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

inline void out() {
	cout<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

bool isout(int h, int w, int H, int W) {
	return ( h<0 || h>=H || w<0 || w>=W );
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


int N;

void input() {
	cin>>N;
}

void solve() {
	cout<<180*(N-2)<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int A[100010][3];
int dp[100010][3];

int main(){
   // freopen("input.txt","r",stdin);

    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>A[i][0]>>A[i][1]>>A[i][2];
    }
    dp[0][0]=A[0][0],dp[0][1]=A[0][1],dp[0][2]=A[0][2];
    for(int i=1;i<n;i++)
    {
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+A[i][0];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+A[i][1];
        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+A[i][2];

    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
    
}

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

int n;
string s, t;

int main()
{
    cin >> n >> s >> t;
    for(int i = 0; i < n; i++){
        if(s.substr(i, n - i) == t.substr(0, n - i)){
            cout << 2 * n - (n - i) << endl;
            return 0;
        }
    }
    cout << 2 * n << endl;


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    // それぞれの地点からスタート、mapで（現在位置、スタート）を保持
    // multisetで横移動の長さを保持
    int H, W;
    cin >> H >> W;

    map<int, int> mp;
    rep(i, W) mp[i] = i;
    multiset<int> vals;
    rep(i, W) vals.insert(0);

    rep(i, H) {
        int l, r;
        cin >> l >> r;
        --l;
        auto it = mp.lower_bound(l);
        int edge = -1; // lとrの中でスタートの右端
        while (it != mp.end() && it->first <= r) {
            edge = max(edge, it->second);
            int x = it->first - it->second;
            mp.erase(it++);
            vals.erase(vals.find(x));
        }
        if (edge >= 0 && r < W) {
            vals.insert(r-edge);
            mp[r] = edge;
        }
        if (vals.empty()) puts("-1");
        else {
            int ans = *vals.begin() + i + 1;
            printf("%d\n", ans);
        }        
    }
    return 0;
}

Measured memory_bytes: 22444
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
#define mkp make_pair
typedef long long ll;
using namespace std;

#include <functional>
#include <climits>

template< typename T>
class SegmentTree{
public:

  using F = function<T(T,T)>;

  int n;
  vector<T> tree;
  const F operation;
  const T def;

  SegmentTree(int size,F _operation,T _def):operation(_operation),def(_def){
    n=1;
    while(n<size) n*=2;
    tree.resize(2*n-1,def);
  }

  void initialize(vector<T> v){
    int vSize=v.size();
    n=1;
    while(n<vSize) n*=2;
    tree.resize(2*n-1,def);

    for(int i=0;i<vSize;i++) tree[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--) tree[i]=operation(tree[2*i+1],tree[2*i+2]);
  }

  void update(int index,T value){
    index+=n-1;

    tree[index]=value;
    while(index>0){
      index=(index-1)/2;
      tree[index]=operation(tree[2*index+1],tree[2*index+2]);
    }
  }

  T query(int a,int b,int k=0,int l=0,int r=-1){//[a,b),getMin(a,b,0,0,-1)
    if(r<0) r=n;

    if(r<=a||b<=l) return def;
    else if(a<=l&&r<=b) return tree[k];
    else{
      T lval=query(a,b,2*k+1,l,(l+r)/2);
      T rval=query(a,b,2*k+2,(l+r)/2,r);
      return operation(lval,rval);
    }
  }
};


int main(){
  int N,Q;
  cin>>N>>Q;
  SegmentTree<int> seg(N,[](int a,int b){return min(a,b);},INT_MAX);
  
  for(int i=0;i<Q;i++){
      int t,x,y;
      cin>>t>>x>>y;
      if(t==0) seg.update(x,y);
      else cout<<seg.query(x,y+1)<<endl;
  }

  return 0;
}



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

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    fenwick_tree<ll> T(N);
    rep(i, N) {
        ll x;
        cin >> x;
        T.add(i, x);
    }
    while (Q--) {
        int t;
        cin >> t;
        if (t == 0) {
            int p, x;
            cin >> p >> x;
            T.add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << T.sum(l, r) << '\n';
        }
    }
    return 0;
}

Measured memory_bytes: 8252
def read():
    return int(input())


def readlist():
    return list(map(int, input().split()))


def readmap():
    return map(int, input().split())


N = read()
A = input()
B = input()
C = input()

cnt = 0
for i in range(N):
    if len({A[i], B[i], C[i]}) == 1:
        pass
    elif len({A[i], B[i], C[i]}) == 2:
        cnt += 1
    else:
        cnt += 2

print(cnt)

Measured memory_bytes: 3064
use std::cmp::*;
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    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_touple<T: std::str::FromStr + Copy>() -> (T, T, T, T) {
    let v: Vec<T> = read_vec();
    assert_eq!(v.len(), 4);
    (v[0], v[1], v[2], v[3])
}

fn main() {
    let (a, b, c, k) = read_touple::<i64>();
    let mut ans = 1 * min(a, k) - max(0, k - a - b);
    println!("{}", ans);
}


Measured memory_bytes: 2168
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<map>
using namespace std;

typedef long long ll;
int modulo = 1000000007; // 10^9 + 7

// 2で割れる回数が0回、1回、2回以上
int quotient(int a) {
	int b = 0;
	if (a % 2 == 0) {
		b++; a /= 2;
		if (a % 2 == 0) { b++; }
	}
	return b;
}

int main() {
	int N; cin >> N;
	int count[3]; for (int i = 0; i < 3; i++) count[i] = 0;

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

	if (count[1] == 0) {
		if (count[2] >= count[0] - 1) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else {
		if (count[2] >= count[0]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159;
int main()
{
    long long int n,m,a=0,b,i;
    cin>>n>>m;
    for(i=0; i<m; i++)
    {
        cin>>b;
        a+=b;
    }
    if(a>n)
        cout<<"-1"<<endl;
    else
        cout<<n-a<<endl;

    return 0;
}


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

int main() {
  long long k, n;
  cin>>k>>n;
  long long a[n];
  for (int i=0; i<n; i++) cin>>a[i];
  long long tmp = 0;
  for (int i=0; i<n-1; i++) {
    tmp = max(a[i+1] - a[i], tmp);
  }
  tmp = max(k-a[n-1]+a[0], tmp);
  cout<<k-tmp<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    ll N,K;
    cin >> N >> K;
    vec<int> A(N);
    rep(i,N) {
        cin >> A[i];
        --A[i];
    }
    if(K<=N){
        int now = 0;
        rep(i,K){
            now = A[now];
        }
        cout << now+1 << endl;
        return 0;
    }
    vec<int> visited(N,0);
    int now = 0;
    int roop = 0;
    int roop1 = 1e9;
    while(true){
        if(visited[now] == 1) roop1=min(roop1,roop);
        if(visited[now] == 2) break;
        ++visited[now];
        now = A[now];
        ++roop;
    }
    K = (K-roop1)%(roop-roop1);

    now = 0;
    rep(i,roop1+K){

        now = A[now];
    }
    cout << now+1 << endl;
}


Measured memory_bytes: 4844
/*
   Aizu Vol-1 0165: Lottery
   2017.8.15 bal4u@uu
   ?´???°??¨?????????
*/

#include <stdio.h>

#define MAX  1000000
#define SQRT 1000     // sqrt(MAX)

char prime[MAX + 5], *p, *q, *pmax = prime + MAX;

int main()
{
	int N, P, M;
	int k, a, b, ans, x;

	for (k = 3, p = prime + 3; k <= SQRT; k += 2, p += 2) {
		if (!*p) {
			for (q = p + k; q <= pmax; q += k) *q = 1;
		}
	}
	while (1) {
		scanf("%d", &N); if (!N) break;
		for (ans = 0, k = 0; k < N; k++) {
			scanf("%d%d", &P, &M);
			a = P - M, b = P + M, x = 0;
			if (a < 2) a = 2;
			if (a == 2) x++, a = 3;
			if (!(a & 1)) a++;
			if (b > 1000000) b = 1000000;
			for (p = prime + a; a <= b; a += 2, p += 2)	if (!(*p)) x++;
			ans += x - 1;
		}
		if (ans < 0) ans = 0;
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1576
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>adj[300001];
    for(int i=0;i<n;i++)
    {
        int b;
        cin>>b;
        adj[b].push_back(i+1);
    }
    if(adj[1].size()==0)
    cout<<-1;
    else
    {
        int x=adj[1][0],y=2,ans=1;
        while(true)
        {
            int f=0;
            if(adj[y].size()>0){
            for(int i=0;i<adj[y].size();i++)
            {
                if(adj[y][i]>x)
                {
                    x=adj[y][i];
                    y++;
                    f=1;
                    ans++;
                    break;
                }
            }
            }
            if(f==0)
            {
                cout<<n-ans;
                return 0;
            }
            
            
        }
    }
}

Measured memory_bytes: 14976
D=int(input())
clist=list(map(int,input().split()))
smat=[[int(x) for x in input().split()] for _ in range(D)]
#print(clist)
#print(smat)

index_set=set(range(26))
for d in range(D):
  max_index=-1
  max_sd=-1
  for i in index_set:
    if max_sd<smat[d][i]:
      max_index=i
      max_sd=smat[d][i]
      
  max_index2=-1
  max_sd2=-1
  for i in range(26):
    if max_sd2<smat[d][i]:
      max_index2=i
      max_sd2=smat[d][i]
      
  if max_index==max_index2:
    print(max_index+1)
    index_set.remove(max_index)
  else:
    if max_sd2>4*max_sd:
      print(max_index2+1)
    else:
      print(max_index+1)
      index_set.remove(max_index)      
      
  if not index_set:
    index_set=set(range(26))
  else:
    max_c=0
    for i in index_set:
      max_c=max(max_c,clist[i])
    if max_c<20:
      index_set=set(range(26))

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

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;

int main() {

    ll A, B, C;
    
    cin >> A >> B >> C;

    ll ans = (A+B) * C / 2;

    cout << ans << endl;


    // if(ans){
    //     cout << "Yes" << endl;
    // }else{
    //     cout << "No" << endl;
    // }

}



Measured memory_bytes: 256