akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1e9;
const long long LINF = 1LL << 50;
#define int long long

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m; cin >> n >> m;
	set<int>a;
	for (int i = 1; i <= sqrt(m); i++) {
		if (m % i == 0) {
			a.insert(i);
			a.insert(m / i);
		}
	}
	int ans = 1;
	for (auto itr = a.begin(); itr != a.end(); itr++) {
		if (*itr*n <= m) {
			ans = *itr;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
name = ['A', 'B', 'C', 'D', 'E']
shop = []
 
while True:
    a,b = map(int, input().split())
    if a == 0 and b == 0:
        break
    shop.append(a+b)
    if len(shop) == 5:
        m = max(shop)
        print(name[shop.index(m)], m)
        shop = []  


Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    string s;
    int a;
    cin >> a >> s;
    int n=0,nn=0;
    for (int i=0;i<a;i++){
        if (s.at(i)=='(') n++;
        if (s.at(i)==')' && n==0) nn++;
        else if (s.at(i)==')') n--;
    }
    string u="";
    for (int i=0;i<nn;i++){
        u.push_back('(');
    }
    for (int i=0;i<n;i++){
        s.push_back(')');
    }
    cout << u+s << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<(int)(n); i++)
#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)
using namespace std;

int main() {
  int A,B,X; cin >>A >>B >>X;
  bool flag=false;
  if (A<=X and X<=A+B) flag=true;
  cout <<(flag ? "YES":"NO") <<endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h> 
 #include <string.h> 
 
 
 int main(){ 
     int m, h; 
     char cards[256], temp[256], result[256]; 
     int i, j=0, len; 
 
 
     while(1){ 
         scanf("%s", cards); 
         len=strlen(cards); 
         if(strcmp(cards, "-")==0&&len==1)break; 
         scanf("%d", &m); 
         for(;m>0;m--){ 
             scanf("%d", &h); 
             strcpy(temp, cards); 
             for(i=0;i<h;i++){ 
                 cards[len-h+i]=temp[i]; 
             } 
             for(i=0;i<len-h;i++){ 
                 cards[i]=temp[i+h]; 
             } 
         } 
         for(i=0;i<len;i++){ 
             result[j++]=cards[i]; 
         } 
         result[j++]='\n'; 
     } 
     result[j]='\0'; 
     printf("%s", result); 
 
 
     return 0; 
 } 



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

int main(){
  while(1){
    int h=0,b=0;
    string r,a;
    cin >> r >> a;
    if(r=="0"&&a=="0")
      break;
    for(int i=0;i<r.size();i++){
      for(int j=0;j<r.size();j++){
        if(r[i]==a[j])
          (i==j)?h++:b++;
      }
    }
    cout << h << " " << b << endl;
  }
  return 0;
}

Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(v) v.begin(), v.end()

int main() {
    //double型で計算するとややこしくなるからintにする
    int64_t A;
    //double B;
    string B;
    cin >> A;
    cin >> B;
    int64_t iB;
    //小数点を文字列の操作で消す
    iB = (B[0]-'0')*100 + (B[2]-'0')*10 + (B[3]-'0');
    
    //小数を2進数表記にすると値が切り捨てられ、小さくなる
    //doubleからintの計算の際に値が小さくなるため+0.5する
    //iB = B * 100 + 0.5;
    
    cout << (A * iB) / 100 << endl;
    return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#include<iomanip>
#include<functional>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<utility>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// 上 左 下 右
const int N=100005,M=1000005,mod=1000000007;
const long long llinf=9223372036854775807ll;
//int & long long
char a,b,c,d;
int main(){
	cin>>a>>b>>c>>d;
	if(a==b||b==c||c==d)
		cout<<"Bad";
	else
		cout<<"Good";
	return 0;
}

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

using namespace std;
using ll = long long;

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

int main(){
    ll n;
    std::cin >> n;
    std::vector<ll> a(n);
    std::vector<std::vector<std::pair<ll, ll>>> fact(n);

    std::cin >> a[0];
    ll g = a[0];
    for(int i = 1; i < n; i++){
        std::cin >> a[i];
        g = gcd(a[i], g);
    }

    // 1つ抜きの最大公約数の最大を求めれば良い
    // まず左からn個の最大公約数
    std::vector<ll> left(n);
    left[0] = a[0];
    for(int i = 1; i < n; i++){
        left[i] = gcd(left[i - 1], a[i]);
    }
    // 右からn個の最大公約数
    std::vector<ll> right(n);
    right[0] = a[n - 1];
    for(int i = 1; i < n; i++){
        right[i] = gcd(right[i - 1], a[n - i - 1]);
    }


    // 1つ抜きの最大公約数の最大値
    // 左端と右端は例外処理
    ll ans = left[n - 1]; // 1つも書き換えない場合
    ans = std::max(ans, left[n - 2]);
    ans = std::max(ans, right[n - 2]);
    for(int i = 1; i < n - 1; i++){
        // i個目を抜く
        ll tmp = gcd(left[i - 1], right[n - i - 2]);
        ans = std::max(ans, tmp);
    }

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 4992
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>

using namespace std;
#define int long  long int
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main()
{
	int a;
	string s;
	cin >> a >> s;
	if (a >= 3200)cout << s;
	else cout << "red";
}

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

int main(){
    string s;
    cin >> s;
    char first = s[0];
    char second = '-';
    int fl = 1;
    int sl = 0;
    for(int i=1;i<4;i++){
        if(s[i]!=first){
            if(second=='-'){
                second = s[i];
                sl++;
            }else if(second!=s[i]){
                cout << "No";
                return 0;
            }else{
                sl++;
            }
            
        }else{
            fl++;
        }
    }
    if(fl==2){cout << "Yes";}else{cout << "No";}
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define rng(a) a.begin(), a.end()
#define ina(n,a) cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]
#define sz(x) (int)(x).size()
#define se second
#define fi first
#define prev            coyhhhhhhyoc    
#define next          sdNNNmNNNNNNNmds  
#define y0           hNNNNy_yNNNNNN_sNh
#define y1          mNNNNNdtdNNNNNNtsNNm
#define yn          mNNNNNNNNy___smNNNms
#define tm            oooooosyysooooot 
#define read               tyhyt        
#define rank              ytmNmo         
#define index              yyy
#define pb push_back
#define pcnt __builtin_popcountll
#define rrep(i,a,b) for(int i = (b); i >= (a); i--)
#define rall(x,a) for(auto x : a)
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string suff, pref;
    cin >> suff;
    int q;
    cin >> q;
    bool rev = false;
    while(q--) {
        int f, t;
        char c;
        cin >> t;
        if(t == 1) {
            rev = !rev;
        } else {
            cin >> f >> c;
            f--;
            if(rev ^ f) {
                suff += c;
            } else {
                pref += c;
            }
        }
    }
    reverse(rng(pref));
    string ans = pref + suff;
    if(rev) {
        reverse(rng(ans));
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;

ll ans[200005];

int main()
{
	int n, k;
	cin >> n >> k;
	double a = n / (k * 1.0);
	int b = int(n / k);
	if(a != b)
	{
		cout << b + 1 << endl;
	}
	else
		cout << b << endl;
	return 0;
} 

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

int main(){
	
 string s;
   cin>>s;
   string t;
    cin>>t;
	 char d=t[t.length()-1];
	  string ss=s+d;
	   if(ss==t)
	    cout<<"Yes";
		else 
		 cout<<"No";	
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a/gcd(a, b) * b;
}

int main()
{
    cout << fixed << setprecision(15);
    ll W, H, N;
    cin >> W >> H >> N;

    vector<ll> X(N);
    vector<ll> Y(N);
    vector<ll> A(N);

    ll minx = 0;
    ll maxx = W;
    ll miny = 0;
    ll maxy = H;

    REP(i, N){
        cin >> X[i] >> Y[i] >> A[i];
        if(A[i] == 1){
            minx = max(minx, X[i]);
        }
        if(A[i] == 2){
            maxx = min(maxx, X[i]);
        }
        if(A[i] == 3){
            miny = max(miny, Y[i]);
        }
        if(A[i] == 4){
            maxy = min(maxy, Y[i]);
        }
    }
    cout << max(maxx-minx,0LL) * max(maxy-miny, 0LL) << endl;
    return 0;
}

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

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main(int argc, char const *argv[]) {
	int n;
	std::cin >> n;
	std::vector<tuple<string,int,int>> v;
	for (size_t i = 0; i < n; i++) {
		string tmps;
		int tmpi;
		std::cin >> tmps >> tmpi;
		v.push_back(make_tuple(tmps,100-tmpi,i+1));
	}
	sort(v.begin(),v.end());
	for (size_t i = 0; i < v.size(); i++) {
		std::cout << get<2>(v[i]) << '\n';
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;cin>>n;
    int a[n][3];
    for(int i=0;i<n;i++)
    {
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    
    int dp[n][3];
    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++)
    {
        for(int j=0;j<3;j++)
        {
            if(j==0)
            dp[i][j]=a[i][j]+max(dp[i-1][1],dp[i-1][2]);
            else if(j==1)
            dp[i][j]=a[i][j]+max(dp[i-1][0],dp[i-1][2]);
            else
            dp[i][j]=a[i][j]+max(dp[i-1][0],dp[i-1][1]);         
        }
    }
    
        int ans=max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
        cout<<ans<<"\n";


}
void tool() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
}
int32_t main() {
	tool();
	
		solve();
	return 0;
}

Measured memory_bytes: 5944
#include<bits/stdc++.h>
using namespace std;
constexpr int64_t mod=1e9+7;

int main()
{
  int64_t a,b,x;
  cin>>a>>b>>x;
  int64_t ans=b/x-a/x;
  if(a%x==0) ans++;
  cout<<ans;
}

Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
n,m = readInts()
A = sorted(readInts())
if n >= m:
    print(0)
else:
    dist = []
    all = 0
    for i in range(m-1):
        dist.append(A[i+1] - A[i])
        all += A[i+1] - A[i]
    dist = sorted(dist, reverse = True)
    print(all - sum(dist[:n-1]))


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

int main()
{
	int n;
	cin >> n;
	vector<int> l(n);
	for (int i=0;i<n;++i)
	{
		cin >> l[i];
	}

	sort(l.begin(),l.end());
	int count=0;
	for (int i=0;i<n;++i)
	{
		for (int j=i+1;j<n;++j)
		{
			for (int k=j+1;k<n;++k)
			{
				if ((l[i]==l[j])||(l[i]==l[k])||(l[j]==l[k]))
				{
					continue;
				}
				if (l[i]+l[j]>l[k])
				{
					++count;
				}
			}
		}
	}
	cout << count << endl;
}







Measured memory_bytes: 3552
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

/*

*/

ll n,k,ans=0;

int main(void){
	cin>>n>>k;
	reg(b,k+1,n){
		if(k==0){
			ans+=(b-k)*(n/b)+max(n-n/b*b-k+1,(ll)0)-1;//0はダメ
		}else{
			ans+=(b-k)*(n/b)+max(n-n/b*b-k+1,(ll)0);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<list>
#include<bitset>
#include<functional>

#define FOR(i, a, b) for(long long int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979

using namespace std;
typedef long long int ll;
typedef pair<long long int, long long int> P;

ll a[100001], t[100001];
ll dp[2][100001];

int main(void) {
	ll n;
	ll keep;
	ll count = 1;
	bool flag = true;

	cin >> n;
	FOR(i, 1, n) {
		cin >> t[i];
	}
	FOR(i, 1, n) {
		cin >> a[i];
	}
	
	keep = t[1];
	dp[0][1]=dp[1][1] = t[1];

	FOR(i, 2, n) {
		if (t[i] == keep) {
			dp[0][i] = 1;
			dp[1][i] = keep;
		}
		else {
			dp[0][i] = dp[1][i] = t[i];
			keep = t[i];
		}
	}

	keep = a[n];
	if (keep > dp[1][n]||keep<dp[0][n]) {
		flag = false;
	}
	else {
		dp[0][n] = dp[1][n] = a[n];
	}
	
	RFOR(i, n-1, 1) {
		if (a[i] == keep) {
			if (dp[0][i] == dp[1][i]) {
				if (a[i] >= dp[1][i]) {
					dp[0][i] = dp[1][i] = 1;
				}
				else {
					flag = false;
				}
			}
			else {
				dp[1][i] = min(dp[1][i], a[i]);
			}
		}
		else {
			keep = a[i];
			if (dp[0][i] == dp[1][i]) {
				if (dp[1][i] == a[i]) {
				}
				else {
					flag = false;
				}
			}
			else {
				if (a[i] <= dp[1][i]) {
					dp[0][i] = dp[1][i] = a[i];
				}
				else {
					flag = false;
				}
			}
		}
	}


	FOR(i, 1, n) {
		count *= dp[1][i] - dp[0][i] + 1;
		if (dp[1][i] - dp[0][i] + 1 <= 0) {
			flag = false;
		}
		count %= MOD;
	}

	if (flag) {
		cout << count << endl;
	}
	else {
		cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << '\n';
typedef int64_t Int;
Int mod = 1e9+7;
Int INF = 1e9+7;

Int par[100001];

Int root(Int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
}

void unite(Int x, Int y) {
    Int rx = root(x);
    Int ry = root(y);
    if (rx == ry) return;
    par[rx] = ry;
}

int main() {
    ios::sync_with_stdio(false);
    Int n;
    cin >> n;
    for (Int i = 0; i < n; i++) par[i] = i;
    vector<pair<Int, Int>> vx(n), vy(n);
    for (Int i = 0; i < n; i++) {
        Int x, y;
        cin >> x >> y;
        vx[i] = {x, i};
        vy[i] = {y, i};
    }
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    priority_queue<tuple<Int, Int, Int>, vector<tuple<Int, Int, Int>>, greater<tuple<Int, Int, Int>>> q;
    for (Int i = 0; i < n - 1; i++) {
        q.push(make_tuple(vx[i + 1].first - vx[i].first, vx[i].second, vx[i + 1].second));
        q.push(make_tuple(vy[i + 1].first - vy[i].first, vy[i].second, vy[i + 1].second));
    }
    Int res = 0;
    for (Int i = 0; i < n - 1; i++) {
        tuple<Int, Int, Int> t = q.top();
        while (root(get<1>(t)) == root(get<2>(t))) {
            q.pop();
            t = q.top();
        }
        unite(get<1>(t), get<2>(t));
        res += get<0>(t);
    }
    dump(res);
    return 0;
} 


Measured memory_bytes: 12400
#include <stdio.h>

int main(){
	int a[4];
	while(1){
    	for(int i = 0; i < 4; ++i){
        	scanf("%d", &a[i]);
    	}
        if(a[0] == 0){ break; }
        
		for(int i = 0; i < 100000; ++i) putchar('(');
		printf("%d+%d+%d+%d", a[0], a[1], a[2], a[3]);
		putchar('\n');
	}
}

Measured memory_bytes: 1028
def main():
    n, t, *s = map(int, open(0).read().split())
    ans = 0
    s = [0] + s
    for i, j in zip(s, s[1:]):
        if j - i >= t:
            ans += t
        else:
            ans += j - i
    else:
        ans += t

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 31592
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <climits>
#include <cmath>
#include <functional>
#include <map>
#include <queue>
#include <set>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

ll n,m;

int main () {
  cin >> n >> m;
  std::vector<ll> a(n),b(n);
  rep(i,n) cin >> a[i];
  priority_queue<ll> q;
  rep(i,n) q.push(a[i]);
  rep(i,m) {
    ll max = q.top();
    q.pop();
    q.push(max/2);
  }
  ll result  = 0;
  rep(i,n) {
    result += q.top();
    q.pop();
  }
  cout << result << endl;
}


Measured memory_bytes: 2936
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
#define mod 1000000007
#define fastio std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define deb(x) cout<<#x<<" "<<x<<endl;
//#define deb(x) cout<<#x<<" "<<x<<" ";
const ll INF = 1e9 + 7;
#define MEM(a,b) memset((a),(b),sizeof(a))

int main () {
  ll n;
  cin>>n;
  std::vector<ll> arr(n);
  for (ll i = 0; i < n; i++) {
    cin>>arr[i];
  }

  unordered_map<ll,ll> first_hash;
  ll first_max_1;
  ll first_max_1_count = 0;
  ll first_max_2_count = 0;
  for (ll i = 0; i < n; i += 2) {
    first_hash[ arr[i] ]++;
  }

  for ( auto it = first_hash.begin(); it != first_hash.end(); ++it ){
    first_max_1_count = max(first_max_1_count , it->second );
    if( first_max_1_count == it->second ) first_max_1 = it->first;
  }
  first_hash.erase(first_max_1);

  for ( auto it = first_hash.begin(); it != first_hash.end(); ++it ){
    first_max_2_count = max(first_max_2_count , it->second );
  }

  unordered_map<ll,ll> second_hash;
  ll second_max_1;
  ll second_max_1_count = 0;
  ll second_max_2_count = 0;
  for (ll i = 1; i < n; i += 2) {
    second_hash[ arr[i] ]++;
  }

  for ( auto it = second_hash.begin(); it != second_hash.end(); ++it ){
    second_max_1_count = max(second_max_1_count , it->second );
    if( second_max_1_count == it->second ) second_max_1 = it->first;
  }
  second_hash.erase(second_max_1);

  //bool flag = 0;
  for ( auto it = second_hash.begin(); it != second_hash.end(); ++it ){
    second_max_2_count = max(second_max_2_count , it->second );
    //flag = 1;
  }

  ll ans = 0;
  ll ans1 = 0;
  ll ans2 = 0;
  // deb(first_max_1_count);
  // deb(first_max_2_count);
  // deb(second_max_1_count);
  // deb(second_max_2_count);
  if(first_max_1 != second_max_1) ans = n - (first_max_1_count + second_max_1_count);
  else{
    ans1 = n - (first_max_1_count + second_max_2_count);
    ans2 = n - (first_max_2_count + second_max_1_count);
    ans = min( ans1 , ans2 );
  }

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


Measured memory_bytes: 5132
#include <bits/stdc++.h>
#define FOR(i, c) for (int i = 0; i < c; i++)
#define MOD 1000000007
using namespace std;

int main() {
  string s;
  cin >> s;
  cout << (s == "ABC" ? "ARC" : "ABC") << endl;
  return 0;
}



Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  string A,B;cin >> A >> B;
  if(A==B) cout << "EQUAL" << endl;
  else if(A.length()>B.length()) cout << "GREATER" << endl;
  else if(A.length()<B.length()) cout << "LESS" << endl;
  else{
    bool isequal = true;
    rep(i,A.length()){
      if(A[i] > B[i]){
        cout << "GREATER" << endl;
        isequal = false;
        break;
      }else if(A[i] < B[i]){
        cout << "LESS" << endl;
        isequal = false;
        break;
      }
    }
    if(isequal)cout << "EQUAL" << endl;
  }
  return 0;
}


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

int main(void){
    int n = 0, m = 0, X = 0, Y = 0;
    int x_max = -100;
    int y_min = 100;

    scanf("%d%d%d%d", &n, &m, &X, &Y);

    for(int i = 0; i < n; i++){
        int tmp = 0;
        scanf("%d", &tmp);
        if(x_max < tmp){
            x_max = tmp;
        }
    }
    if(x_max < X){
        x_max = X;
    }

    for(int i = 0; i < m; i++){
        int tmp = 0;
        scanf("%d", &tmp);
        if(y_min > tmp){
            y_min = tmp;
        }
    }
   if(y_min > Y){
        y_min = Y;
    }

    if(x_max < y_min){
        printf("No War\n");
    }else{
        printf("War\n");
    }

    return 0;

} 


Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <limits.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <typeinfo>
#include <stdlib.h>

using namespace std;

int main(int argc, char* argv[]){
  int n,d,x,cnt=0, tmp;
  cin >> n;
  cin >> d >> x;
  std::vector<int> a(n);
  for (int i=0; i<n; i++){
  	cin >> tmp;
  	cnt += ((d-1)/tmp +1);
  }
  cout << cnt + x << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define dbg(x) cout<<#x"="<<x<<endl

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppi;

#define INF 1000000000



int main(){
  while(true){
    int n,m;
    cin >> n >> m;
    if(n==0 && m==0) break;

    vector<int> t,h; //taro, hanako
    int st=0,sh=0; //sum of taro,hanako
    rep(i,n){
      int d;
      scanf("%d", &d);
      t.pb(d);
      st+=d;
    }
    rep(i,m){
      int d;
      scanf("%d", &d);
      h.pb(d);
      sh+=d;
    }

    sort(t.begin(), t.end());
    sort(h.begin(), h.end());

    if((st+sh)%2==1){
      cout << -1 << endl;
      continue;
    }

    int target = (st+sh)/2;
    rep(i,n){ //try (taro to hanako t[i])
      int search = -target+t[i]+sh;
      if(*(lower_bound(h.begin(), h.end(), search)) == search){
	cout << t[i] << " " << search << endl;
	break;
      } else if(i==n-1){
	cout << -1 << endl;
      }
    }

  }

}

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

#define ll long long
#define T int t, q=0; cin>>t; while(q++<t)

int main()
{
    string s;
    cin>>s;
    if(s[2]==s[3] && s[4]==s[5]) cout<<"Yes";
    else cout<< "No";
}


Measured memory_bytes: 256
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      double a = Double.parseDouble(st.nextToken());
      double b = Double.parseDouble(st.nextToken());
      int h = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      
      double hangle = ((double)((h%12)*30 + 360) + (double)m/2.0)%360;
      double mangle = (double)m*6.0;
      
      double hr = Math.toRadians((double)hangle);
      double mr = Math.toRadians((double)mangle);
      
      double hx = a*Math.cos(hr);
      double hy = a*Math.sin(hr);
      double mx = b*Math.cos(mr);
      double my = b*Math.sin(mr);
      
      //double answer = Math.sqrt((mx-hx)*(mx-hx) + (my-hy)*(my-hy));
      double answer = Math.sqrt(a*a+b*b-2*a*b*Math.cos(mr-hr));
      out.println(answer);
      
      
      
      
      
      
      
      
      
      out.close();
   }
   
      
}

Measured memory_bytes: 33524
import sys;
import numpy as np;
sys.stdin.readline()
a=np.sort(np.array(sys.stdin.readline()[:-1].split(),dtype=np.int32))[::-1]
if a.size%2:
 a=np.append(a,0)
a=np.reshape(a,(-1, 2)).T
print(np.sum(a[0]-a[1]))


Measured memory_bytes: 15672
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,k,l,d[10]={};
    cin>>n>>k;
    for(int i=0;i<k;i++){
        cin>>l;
        d[l]=1;
    }
    bool flag=true;
    int x;
    while(flag){
        flag=false;
        x=n;
        while(x>0){
            if(1==d[x%10]){
                n++;
                flag=true;
                break;
            }
            x/=10;
        }
    }
    cout<<n;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

#define INF (INT_MAX/2)
using namespace std;

struct Edge {
  int src, dst, weight;
  Edge(int src, int dst, int weight) :
    src(src), dst(dst), weight(weight) { }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

bool bellmanford(const Graph g, int s, vector<int> &dist) {
  int V = g.size();
  dist.assign(V, INF);
  dist[s] = 0;
  
  bool negative_cycle = false;
  for(int k = 0; k < V; k++) for(int i = 0; i < V; i++){
    if(dist[i] >= INF) continue;
    for(vector<Edge>::const_iterator e = g[i].begin(); e != g[i].end(); e++){
      if (dist[e->dst] > dist[e->src] + e->weight) {
        dist[e->dst] = dist[e->src] + e->weight;
        if (k == V - 1) {
          dist[e->dst] = -INF;
          negative_cycle = true;
        }
      }
    }
  }
  return !negative_cycle;
}

int main(){
  int V, E, r, s, t, w;
  cin >> V >> E >> r;
  Graph g(V);
  vector<int> dist;

  while(E--){
    cin >> s >> t >> w;
    g[s].push_back(Edge(s, t, w));
  }
  if(!bellmanford(g,r,dist)) cout << "NEGATIVE CYCLE" << endl;
  else{
    for(int i = 0; i < V; i++){
      if(dist[i] >= INF) cout << "INF" << endl;
      else cout << dist[i] << endl;
    }
  }
}

Measured memory_bytes: 1324
//2019年12月8日現在

#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>
#include<iomanip>
#include<limits>
#include<thread>
#include<map>
#include<stack>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<tuple>
#include <cstdio>

using namespace std;

template <class... A>
void prints() { cout << "\n"; }
template <class... A>
void prints_rest() { cout << "\n"; }
template <class T, class... A>
void prints_rest(const T &first, const A &... rest) { cout << " " << first; prints_rest(rest...); }
template <class T, class... A>
void prints(const T &first, const A &... rest) { cout << first; prints_rest(rest...); }

namespace {
    // printElms(&a[0], a[n]);　みたいな感じで使う。
    void printElems(const int* begin, const int* end)
    {
        for (const int* p = begin; p != end; ++p) {
            std::cout << *p << ' ';
        }
        std::cout << std::endl;
    }
}



#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n+1; i++)
#define repr(i,n) for(int i=n-1; i>=0; i--)
#define repr1(i,n) for(int i=n; i>0; i--)
#define souatari rep1(i,n-1)rep(j,i)
#define souatari1 for(int i=2; i<n+1; i++)rep1(j,i-1)
#define mp make_pair
#define F first
#define S second
#define elif else if

typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef array<int,3> arr3;
typedef long double D;


const ll llinf =  numeric_limits<ll>::max();
const ll _llinf = numeric_limits<ll>::lowest();
const int inf = numeric_limits<int>::max();
const int _inf = numeric_limits<int>::lowest();
const double dinf = numeric_limits<double>::infinity();
const ll MOD = 1000000007;
const ll BIG = 10000000000000000;




int main(){
    int n;
    cin >> n;
    priority_queue<pll, vector<pll>, greater<pll> > q;
    rep(i,n){
        
        ll tmpf,tmps;
        cin >> tmpf >> tmps;
        q.push(mp(tmpf+tmps,tmpf-tmps));
    }
    ll t = _llinf;
    int cnt = 0;
    while(!q.empty()){
        pll tmp = q.top();
        q.pop();
        if (tmp.S >= t) {
            t = tmp.F;
            cnt++;
        }
    }

    prints(cnt);

    return 0;
}

Measured memory_bytes: 2420
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

int INF=10000*100000+100;
const int MAX_V=100005;

using namespace std;

struct edge{int to, cost;};
typedef pair<int,int> P;
vector<edge> G[MAX_V];
long long int d[MAX_V];
int V,E,s;


main(){
    scanf("%d%d%d",&V,&E,&s);
    for (int i=0; i<E; i++) {
        int from, to, cost;
        scanf("%d", &from);
        scanf("%d", &to);
        scanf("%d", &cost);
        edge edge;
        edge.to = to;
        edge.cost = cost;
        G[from].push_back(edge);
    }
    
    priority_queue<P,vector<P>,greater<P> > que;
    fill(d,d+V,INF);
    d[s]=0;
    que.push(P(0,s));
    
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v]< p.first) continue;
        for(int i=0; i<G[v].size(); i++){
            edge edge = G[v][i];
            if(d[edge.to]>d[v]+edge.cost){
                d[edge.to]=d[v]+edge.cost;
                que.push(P(d[edge.to],edge.to));
            }
        }
    }
    
    for(int i=0; i<V;i++){
        if(d[i]==INF)printf("INF\n");
        else printf("%lld\n",d[i]);
    }
}



Measured memory_bytes: 13468
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define ALL(V) ((V).begin(),(V).end())
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
const int vx[4]={0,1,0,-1},vy[4]={1,0,-1,0};
using namespace std;

int main(){
  int N,M,ans=0;
  cin>>N>>M;
  int X[M],Y[M],CNT[N];
  REP(i,M) cin>>X[i]>>Y[i];
  REP(i,N) CNT[i]=1;
  
  bool CAN[N];
  REP(i,N) CAN[i]=false;
  CAN[0]=true;
  
  REP(i,M){
    if(CAN[X[i]-1]==true){
      CAN[Y[i]-1]=true;
      if(CNT[X[i]-1]==1) CAN[X[i]-1]=false;
    }
    CNT[X[i]-1]--;
    CNT[Y[i]-1]++;
  }
  
  REP(i,N){
    if(CAN[i]==true) ans++;
  }
  
  cout<<ans<<endl;
  return 0;
}

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

using namespace std;

typedef long long int ll;
typedef long long int lli;
typedef unsigned long long int ull;
typedef long double ld;
typedef string str;

typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<ll> vll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = 1; i <= (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define mp(p, q) make_pair(p, q)
//３つ以上の値をセットに(3より多いときはカッコ内を増やす)\
sort -> p -> q -> r
#define mt(p, q, r) make_tuple(p, q, r)
#define all(a) a.begin(), a.end()

template <typename T>
void V(T &n)
{
  for (ll i = 0; i < n.size(); i++)
  {
    cin >> n[i];
  }
}

template <typename T, typename U>
void V2(T &n, U &m)
{
  for (ll i = 0; i < n.size(); i++)
  {
    cin >> n[i] >> m[i];
  }
}

template <typename T>
void Sort(T &n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (sort(n.begin() + a, n.end()));
  }
  else
  {
    return (sort(n.begin() + a, n.begin() + b));
  }
}

//配列を反転
template <typename T>
void Reve(T &n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (reverse(n.begin() + a, n.end()));
  }
  else
  {
    return (reverse(n.begin() + a, n.begin() + b));
  }
}

template <typename T>
void Down(T &n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (sort(n.begin() + a, n.end(), greater<ll>()));
  }
  else
  {
    return (sort(n.begin() + a, n.begin() + b, greater<ll>()));
  }
}

  void Main()
  {
    char a; cin >> a;
    if(a == 'T') fin('A')
    else if(a == 'A') fin('T')
    else if(a == 'C') fin('G')
    else fin('C')
  }

  int main()
  {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20); //高精度少数表示
    Main();
    return 0;
  }

Measured memory_bytes: 256
n=int(input())
arr1=list(map(int,input().split()))
arr2=arr1[:]
ans1=0
ans2=0

if arr1[0]<=0:
    ans1+=abs(arr1[0])+1
    arr1[0]=1
if arr2[0]>=0:
    ans2+=arr2[0]+1
    arr2[0]=-1

sum1=arr1[0]
for i in range(1,n):
    tmp=sum1+arr1[i]
    if i%2==1:
        if tmp>=0:
            ans1+=tmp+1
            sum1=-1
        else:
            sum1=tmp
    else:
        if tmp<=0:
            ans1+=abs(tmp)+1
            sum1=1
        else:
            sum1=tmp
sum2=arr2[0]
for i in range(1,n):
    tmp=sum2+arr2[i]
    if i%2==0:
        if tmp>=0:
            ans2+=tmp+1
            sum2=-1
        else:
            sum2=tmp
    else:
        if tmp<=0:
            ans2+=abs(tmp)+1
            sum2=1
        else:
            sum2=tmp
print(min(ans1,ans2))

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

void ccp(vector<int>& c, int n, int m){
  sort(c.begin(), c.end());
  vector<vector<int> > t(m, vector<int>(n + 1));
  for(int i = 0; i < m; i++){
    t[i][0] = 0;
  }
  for(int j = 0; j <= n; j++){
    t[0][j] = j;
  }
  for(int i = 1; i < m; i++){
    for(int j = 0; j <= n; j++){
      if(j - c[i] < 0) t[i][j] = t[i - 1][j];
      else t[i][j] = min(t[i - 1][j], t[i][j - c[i]] + 1);
    }
  }
  cout << t[m - 1][n] << endl;
  return;
}

void kp(vector<int>& v, vector<int>& w, int N, int W){
  vector<pair<int, int> > k(N);
  for(int i = 0; i < N; i++){
    k[i].second = v[i];
    k[i].first = w[i];
  }
  sort(k.begin(), k.end());
  vector<vector<int> > t(N, vector<int>(W + 1));
  for(int i = 0; i < N; i++){
    t[i][0] = 0;
  }
  for(int i = 0; i <= W; i++){
    if(i >= k[0].first) t[0][i] = k[0].second;
    else t[0][i] = 0;
  }
  for(int i = 1; i < N; i++){
    for(int j = 0; j <= W; j++){
      if(j - k[i].first < 0) t[i][j] = t[i - 1][j];
      else t[i][j] = max(t[i - 1][j], t[i - 1][j - k[i].first] + k[i].second);
    }
  }
  cout << t[N - 1][W] << endl;
}

void lis(vector<int>& a){
  int n = a.size();
  vector<int> l(n);
  l[0] = a[0];
  int lid = 1;
  for(int i = 1; i < n; i++){
    int x = a[i];
    auto it = lower_bound(l.begin(), l.begin() + lid, x);
    int pos = (int)(it - l.begin());
    if(pos == lid){
      l[lid++] = x;
    }
    else *it = x;
    /*for(int i = 0; i < l.size(); i++){
      cout << l[i] << " ";
    }
    cout << endl;*/
  }
  cout << lid << endl;
}

void solve(){
  int n; cin >> n;
  vector<int> v(n);
  for(int i = 0; i < n; i++) cin >> v[i];
  lis(v);
}

int main(){
  solve();
  return 0;
}



Measured memory_bytes: 3568
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cctype>
#include<cstring>
#define maxn 2007
#define SDOI2020 RP++ 
using namespace std;
int a,b,c; 
inline int read()
{
	int x=0;
	int flag=0;
	char ch;
	ch=getchar();
	while(!isdigit(ch)) 
	{
		if(ch=='-') flag=1;
	ch=getchar();	
	}
	while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
		}
		if(flag==1) x=-x;	
		return x;
}


int main()
{
	a = read();
	b = read();
	c = a * (a - 1) / 2 + b * (b - 1) / 2;
	cout<<c<<endl; 
	
	return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(cnt,e) for(ll cnt=0;cnt<e;cnt++ )
typedef pair<ll,ll> P;
const ll mod = 1e9+7;
const ll INF = INT64_MAX;

ll i,j,k;


int main(){
   ll x;
   cin>>x;
   if(x<1200)cout<<"ABC"<<endl;
   else cout<<"ARC"<<endl;

}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,c,d;
int sum[105];
int main()
{
	int ans=0;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	for(int i=a+1;i<=b;i++)
	sum[i]++;
	for(int i=c+1;i<=d;i++)
	sum[i]++;
	for(int i=a;i<=d;i++)
	if(sum[i]>1)ans++;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 128
def calc_height(xs, ys, hs, cx, cy):
    ret = -1
    zeros = []
    for i in range(len(xs)):
        x = xs[i]
        y = ys[i]
        h = hs[i]
        if h == 0:
            zeros.append((x,y,h))
            continue
        a = abs(x - cx)
        b = abs(y - cy)
        ch = h + a + b
        if ret == -1:
            ret = ch
        else:
            if ret != ch:
                return -1
    for x, y, h in zeros:
        a = abs(x - cx)
        b = abs(y - cy)
        if ret - a - b > 0:
            return -1
    return ret


def solve(xs, ys, hs):
    for cx in range(101):
        for cy in range(101):
            h = calc_height(xs, ys, hs, cx, cy)
            if h > 0:
                return cx, cy, h


n = int(input())
xs = []
ys = []
hs = []
for i in range(n):
    x, y, h = list(map(int, input().split(' ')))
    xs.append(x)
    ys.append(y)
    hs.append(h)


print(' '.join([str(q) for q in solve(xs, ys, hs)]))

Measured memory_bytes: 3064
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll X,Y,Z,K;
  cin >> X >> Y >> Z >> K;
  vl A(X),B(Y),C(Z);
  rep(i,X){
    cin >> A[i];
  }
  rep(i,Y){
    cin >> B[i];
  }
  rep(i,Z){
    cin >> C[i];
  }
  vl D(X*Y);
  rep(i,X){
    rep(j,Y){
      D[i+X*j]=A[i]+B[j];
    }
  }
  sort(D.begin(),D.end());
  sort(C.begin(),C.end());
  reverse(D.begin(),D.end());
  reverse(C.begin(),C.end());
  vl ND(min(K,X*Y));
  rep(i,(ll)ND.size()){
    ND[i]=D[i];
  }
  vl E((ll)ND.size()*Z);
  rep(i,(ll)ND.size()){
    rep(j,Z){
      E[i+ND.size()*j]=ND[i]+C[j];
    }
  }
  sort(E.begin(),E.end());
  reverse(E.begin(),E.end());
  rep(i,K){
    cout << E[i] << endl;
  }
}

Measured memory_bytes: 34640
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>

using namespace std;

int solve(int n) {
	int ret = 0;
	while (n) {
		ret += n % 10;
		n /= 10;
	}
	return ret;
}

int main() {
	int n;
	cin >> n;
	printf("%s\n", (n%solve(n) == 0) ? "Yes" : "No");
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
using namespace std;
long long sum,a[1000000],n,ans,ans1,last;
void solve1(){
	if (sum<=0){
		ans+=1-sum;
		sum=1;
	}
}
void solve2(){
	if (sum>=0){
		ans+=sum+1;
		sum=-1;
	}
}
void solve(int f){
	for (int i=0;i<n;i++){
		sum+=a[i];
		if (i%2==f)
			solve1();
		else
			solve2();
	}
}
int main()
{
	cin>>n;
	for (int i=0;i<n;i++) cin>>a[i];
	solve(0);
	ans1=ans;sum=ans=0;
	solve(1);
	cout<<min(ans,ans1);
	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<set>
#include<string>
#include<iostream>
#include<vector>
using namespace std;

int main(){
    int N, Q, qi;
    string S;
    char c;
    cin >> N;
    cin >> S;
    cin>>Q;
    vector<set<int>> is(26);
    for (int i = 0; i < N; i++)
    {
        is[S[i] - 'a'].insert(i);//Sのi番目の文字の欄に何番目に出たかを記録
    }
    int l, r;
    for (int i = 0; i < Q; i++)
    {
        cin >> qi;
        if (qi == 1)
        {
            int ind;
            char c;
            cin >> ind >> c;
            ind--;
            is[S[ind] - 'a'].erase(ind);//S[i]がind番目に出るという情報を削除
            S[ind] = c;//Sの情報を書き換え
            is[S[ind]-'a'].insert(ind);//c(=S[i]-'a')がind番目に出るという情報を追加
        }
        else
        {
            cin >> l >> r;
            int ans = 0;
            l--;
            for (int i = 0; i < 26; i++)
            {
                //i番目の文字がｌ何番目以降（i番目含む）に初めて出る場所を調べる
                auto itr = is[i].lower_bound(l);
                //それが指定範囲内にあれば
                if(itr != is[i].end() && *itr < r)
                {
                    ans++;
                }
                
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 24196
import sys
input = sys.stdin.readline

S = input()

alphabets = set(chr(ord('a')+x) for x in range(26))

def F(S,alphabets):
    if len(S) == 0:
        return -1
    T = F(S[1:],alphabets-set([S[0]]))
    if T == -1:
        larger = [x for x in alphabets if x > S[0]]
        if not larger:
            return -1
        return min(larger)
    return S[0] + T

answer = F(S,alphabets)
print(answer)


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

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define MOD 1e9+7
#define sp ' '


using ll = long long;


ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b, q;
    cin >> a >> b >> q;

    vector<ll> s(a+2), t(b+2);
    s[0] = -1e18;
    s[a+1] = 1e18;
    t[0] = -1e18;
    t[b+1] = 1e18;

    rep(i, a){
        cin >> s[i+1];
    }
    rep(i, b){
        cin >> t[i+1];
    }


    rep(i, q){
        ll ans = LLONG_MAX;
        ll x; cin >> x;
        auto sitr = upper_bound(s.begin(), s.end(), x);
        auto titr = upper_bound(t.begin(), t.end(), x);
        ll sh[2] = {*(sitr-1), *sitr};
        ll te[2] = {*(titr-1), *titr};

        for(int i = 0; i < 2; ++i){
            for(int j = 0; j < 2; ++j){
                ll tmps = abs(x-sh[i]) + abs(sh[i]-te[j]);
                ll tmpt = abs(x-te[i]) + abs(te[i]-sh[j]);
                ans = min(ans, min(tmps, tmpt));
            }
        }
        ppp(ans);
    }

    return 0;
}


Measured memory_bytes: 2944