akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < n; i++)

const double PI=3.141592653589793;

int main()
{
  char alfa;
  cin >> alfa;

  if((alfa>='a')&&(alfa<='z'))
    cout << "a" << endl;
  else
    cout << "A" << endl;

  return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int N;
    cin>>N;
    int A[N],B[N];
    rep(i,N){
        cin>>A[i]>>B[i];
    }

    if(N%2==1){
        sort(A,A+N);
        sort(B,B+N);
        int x=N/2;
        int ans=max(0LL,B[x]-A[x]+1);

        cout << ans << endl;



    }else{
        sort(A,A+N);
        sort(B,B+N);
        int x=N/2-1;
        int ans=max(0LL,B[x]+B[x+1]-A[x]-A[x+1]+1);
        cout << ans << endl;
    }

    



}


Measured memory_bytes: 6788
#include<bits/stdc++.h>
using namespace std;
#include <math.h>
#define ll long long 
// to increase precision
// std::cout<<std::fixed;
// 	std::cout<<std::setprecision(6)<<z;
#define max1 1000001

//long long int mod=1e18 ;




int main(){	
	int k;
	string s;
	cin>>k>>s;
	int n=s.length();
	if(n<=k){
		cout<<s<<endl;
	}
	else{
		for(int i=0;i<k;i++){
			cout<<s[i];
		}
		for(int i=0;i<3;i++){
			cout<<".";
		}
	}

		
}
	
	
	
	





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

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

  if(N % (D * 2 + 1) == 0){
    cout << N / (D * 2 + 1) << endl;
  }

  else{
    cout << N / (D * 2 + 1) + 1 << endl;
  }
}

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

int main() {
  int a, b;
  cin >> a >> b;
  if ((a*b)%2==0){
    cout << "Even" << endl;
  } else cout << "Odd" << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef   long long int ll;
typedef unsigned long long int sll;
typedef  long double ld;
typedef tree <int,null_type,less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define rep(g, i, n) for (ll g = i; g < n; g++)
#define rev(g, n, i) for (ll g = n - 1; g >= i; g--)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(), v.end()
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
 
#define um unordered_multiset
#define us unordered_set
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define rem 500009
#define PI 3.1415926535
#define INF 1000000000000 
ll n,m,k=0,z,cnt=0;
ll A=1000000007;
ll a[2000005];
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
bool cmp(pair<int,int>a,pair<int,int>b)
{
    if(a.second!=b.second)return a.second<b.second;
    
    else{return a.first<b.first;}
}
void solve()
 { ll d,t,s;
               cin>>d>>t>>s;   
               if(s*t>=d){cout<<"Yes";}
               else{cout<<"No";}
 }
 
 
 
int main()
{ FAST;
 
    ll tt=1;
 

//cin>>tt;
    
    while(tt--){
                           solve();
    }
    return 0;
}


Measured memory_bytes: 3628
import numpy as np


def solve():
    n, x = [int(i) for i in input().split()]
    l = np.array([int(i) for i in input().split()])

    if x == 0:
        print(0)
        exit(0)

    d = 0
    ans = 1

    for i in range(1, n + 1):
        d = d + l[i - 1]
        if d <= x:
            ans += 1
        else:
            break

    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 14444
N=int(input())
A=list(map(int,input().split()))
import collections as col

sa=set(A)
ca=col.Counter(A)
num=0
for i in sa:
    if ca[i]==1:
        continue
    else:
        num += (ca[i]*(ca[i]-1))//2
for i in A:
    ans = num - (ca[i]-1)
    print(ans)

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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repr(i,x,n) for(int i=(x);i<(n);i++)
#define sortn(a) sort(a.begin(),a.end())
#define sortr(a) sort(a.begin(),a.end(),greater<int>())

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main(){
    
    int n;
    cin >> n;
    vi a(n);
    rep(i,n){
        cin >> a[i];
        a[i] = -a[i];
    }
    vi p;
    int idx;

    rep(i,n){
        idx = upper_bound(p.begin(),p.end(),a[i]) -p.begin();
        if(idx != p.size()){
            p[idx] = a[i];
        }else{
            p.push_back(a[i]);
        }
    }

    cout << p.size() << endl;
    
    return 0;
}



Measured memory_bytes: 1276
text  = input()

result = ''
for i in range(len(text)):
    code = ord(text[i])
    if ord('A') <= code <= ord('Z'):
        result += chr(code + 32)
    elif ord('a') <= code <= ord('z'):
        result += chr(code - 32)
    else:
        result += chr(code)
print(result)

Measured memory_bytes: 6724
w, a, b = map(int, input().split())

if a < b:
    if b <= a + w:
        print(0)
    else:
        print(b - (a + w))
elif a > b:
    if a <= b + w:
        print(0)
    else:
        print(a - (b + w))
else:
    print(0)

Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int cake = 0; cake <= 20; cake++) {
			for (int donut = 0; donut <= 15; donut++) {
				if (cake*4 + donut*7 == n) {
					System.out.println("Yes");
					return;
				}
			}
		}
		System.out.println("No");
	}
}


Measured memory_bytes: 21844
#include <stdio.h>
#include <stdlib.h>

int comp(const void *a, const void *b)
{
  long *A = (long *)a;
  long *B = (long *)b;
  if(*A > *B) return 1;
  if(*A < *B) return -1;
  return 0;
}

int main(void)
{
  int N;
  scanf("%d", &N);
  long A[N];
  for(int i = 0; i < N; i++){
    scanf("%ld", &A[i]);
    A[i] -= i+1;
  }
  qsort(A, N, sizeof(long), comp);
  long ans = 0;
  for(int i = 0; i < N; i++)
    ans += abs(A[N/2]-A[i]);
  printf("%ld\n", ans);
}


Measured memory_bytes: 3324
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

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 N, M;
ll k;

//��@
void solve() {
	cin >> N;
	vector<ll> vec(N);
	ll sum=0;
	rep(i,N) {
		cin >> vec[i];
		sum+=vec[i];
	}
	ll ans = sum;
	ll tsum=0;
	rep(i,N-1){
		tsum+=vec[i];
		ans = min(ans,abs(sum-tsum -tsum));
	}

	cout << ans;
	
	return;
}

int main() {

	//����

	solve();
	cout << endl;
	return 0;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }
void ans1(bool x){
  if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){
  if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){
  if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x, ll y, ll z){
  if(x) cout<<y<<endl;else cout<<z<<endl;}   


int main(){
  ll i,j;
  //ll n; cin>>n;
  ll a,b,c,d,e,f; cin>>a>>b;
  //ll a,b,c,d,e,f; cin>>a>>b>>c;
  //ll a,b,c,d,e,f; cin>>a>>b>>c>>d;
  //string s; cin >> s;
  ll result = 0;
  ll buf = 0;
  bool judge = true;
  ans1(a%500<=b);

  /*
  vector<ll> a(n);
  for(i=0;i<n;i++){
    cin >> a[i];
  }
  
  for(i=0;i<n;i++){

  }
  */

  return 0;
}

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

using namespace std;

int n;
char s1[200];
char s2[200];
int main()
{
    cin >> n;
    int count1 = 0,count2=0;
    
    for(int i = 0;i<n;i++){
        cin >> s1;
        cin >> s2;
        if(strcmp(s1,s2)>0){
            count1 += 3;
        }else if(strcmp(s1,s2)== 0){
            count1+=1;
            count2+=1;
        }else{
            count2+=3;
        }
    }
    cout << count1 << " " << count2 << endl;


    return 0;
}



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

#define rep(i,n) for(int i=0;i<(n); ++i)
#define INF 100000 // 2^31-1
#define MAX_V 100000


using namespace std;

using ll =long long;
using P = pair<int,int>;


 
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

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

int gettt(long long int num){
    int digit=0;
if(num<10){
digit=0;
}else{
    while(num>1){
        num /= 10;
        digit++;
    }
}
    return digit;
}

int main() {

ios::sync_with_stdio(false);
cin.tie(0);
	int n;
cin>>n;
long long int a[n];
long long int res=1;

for(int i=0;i<n;i++){
cin>>a[i];

}
sort(a,a+n);

if(a[0]==0){
cout<<0<<endl;
return 0;
}

for(int i=0;i<n;i++){
res*=a[i];
if(res>1000000000000000000 || res<=0){
cout<<-1<<endl;
return 0;
}
}

cout<<res<<endl;

}
//double res=10.11;
//printf("%.10f",ans);
//cout << fixed << setprecision(5) <<(n*2)*M_PI << endl;


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

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

    vector<int> s((1<<n));
    for(int i=0; i<(1<<n); i++){
        cin >> s[i];
    }
    sort(s.begin(), s.end());
    reverse(s.begin(), s.end());
    //for(int slime : s) cout << slime << " ";
    //cout << endl;

    multiset<int> parents;
    parents.insert(s[0]);

    vector<int> already_generated((1<<n));
    already_generated[0] = 1;

    for(int i=0; i<n; i++){
        int slime = 0;
        auto itr = parents.rbegin();
        multiset<int> child;

        while(itr != parents.rend()){
            //cout << *itr << " ";
            while(already_generated[slime] == 1 || s[slime] >= *itr){
                slime += 1;

                if(slime == (1<<n)){
                    //for(int c : child) cout << c << " ";
                    //cout << endl; 
                    cout << "No" << endl;
                    return 0;
                }
            }
            child.insert(s[slime]);
            already_generated[slime] = 1;
            itr = next(itr);
        }
        //cout << endl;
        for(int c : child) parents.insert(c);
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 23780
#include <iostream>

using namespace std;

int main(){
  int a, b;
  std::cin >> a >> b;
  if( a > 12 ){
    std::cout << b << '\n';
  }else if( 6 <= a && a <= 12 ){
    std::cout << b/2 << '\n';
  }else {
    std::cout << 0 << '\n';
  }
  return 0;
}


Measured memory_bytes: 256
//参考：https://qiita.com/DaikiSuyama/items/9dba963ba74396b9b7fd
//インクルード(アルファベット順)
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <iterator>      //集合演算(積集合,和集合,差集合など)
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define FIR first    //pairの一つ目の要素
#define SEC second   //pairの二つ目の要素

signed main()
{
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vector<int> A(N);
    REP(i, N)
    {
        cin >> A[i];
    }

    set<int> K(ALL(A));
    cout << SIZE(K) << endl;

    return 0;
}


Measured memory_bytes: 3660
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

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

  int odd = 0, even = 0, four = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (a & 1) {
      odd++;
    } else {
      even++;
    }
    if (a % 4 == 0) {
      four++;
    }
  }

  bool is_ok = true;
  if (odd > four + 1) {
    is_ok = false;
  } else if (odd == four + 1) {
    if (four == even) {
      is_ok = true;
    } else {
      is_ok = false;
    }
  } else {
    is_ok = true;
  }
  cout << (is_ok ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int c=0,i,j,mx=0;
  int a[n];
  cin>>a[0];
  for(i=1;i<n;i++)
  {
    cin>>a[i];
    if(a[i]<=a[i-1])
    c++;
    else
    {
      mx=max(mx,c);
      c=0;
    }
  }
  mx=max(c,mx);
  cout<<mx;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main(){
  int N,m=0;
  cin >> N;
  while (N%10==0 && N>10) {
    N/=10;
  }
  if (N==10) {
    cout << 10 << endl;
  } else {
    m=0;
    while (N>0) {
      m+=N%10;
      N/=10;
    }
    cout << m << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn = 100005;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f;
const double eps = 1e-9;

int n,m,q;
char s[maxn];
int num[maxn];

int main()
{
    while(~scanf("%s",s))
    {
        mst(num,0);
        int len=strlen(s);
        for(int i=0;i<len;i++)
        {
            num[s[i]-'a']++;
        }
        int flag=0;
        int ans=-1;
        for(int i=0;i<26;i++)
        {
            if(num[i]==0)
            {
                flag=1;
                ans=i;
                break;
            }
        }
        if(flag)
        {
            printf("%c\n",'a'+ans);
        }
        else puts("None");
    }
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
/*
#include<algorithm>
#include<array>
#include<cassert>
#include<cmath>
#include<cstdlib>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<typeinfo>
#include<utility>
#include<vector>
*/
#define int long long int
#define double long double
using namespace std;
#define INT_DMAX 1000000007
#define INF 1000000000000000007
const int MAX_N = 1 << 17;
#define rep(i, n) for (int(i) = 0, i##_len = (n); (i) < i##_len; (i)++)
#define reps(i, x) for (int(i) = 1; (i) <= (int)(x); (i)++)
#define rrep(i, x) for (int(i) = ((int)(x)-1); (i) >= 0; (i)--)
#define rreps(i, x) for (int(i) = ((int)(x)); (i) > 0; (i)--)
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); (i)++)
#define pb push_back
#define mp make_pair
#define bit(n) ((int)(1) << (n))
#define all(x) (x).begin(), (x).end()
#define debug(x) std::cout << #x << ": " << (x) << std::endl
#define nint int
using namespace std;

int dy[] = {0, 0, 1, -1, 0};
int dx[] = {1, -1, 0, 0, 0};
typedef pair<int, int> pii;
typedef pair<double, double> dop;
template <class T>
bool chmax(T& a, const T& b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b)
{
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
struct aaa {
    aaa()
    {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} aaaaaaa;

struct node {
    std::vector<pair<int, int>> nextnode;
};


signed main()
{
    int n;
    std::cin >> n;
    std::vector<node> tree(n);
    std::vector<int> dist(n, INF);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        pii pa = mp(a, c);
        pii pb = mp(b, c);
        tree[a].nextnode.pb(pb);
        tree[b].nextnode.pb(pa);
    }
    int q, k;
    std::cin >> q >> k;
    k--;
    std::queue<int> calc;
    calc.push(k);
    dist[k] = 0;
    while (!calc.empty()) {
        int now = calc.front();
        calc.pop();
        for (int i = 0; i < tree[now].nextnode.size(); i++) {
            int next = tree[now].nextnode[i].first;
            int nextcost = tree[now].nextnode[i].second;
            if (dist[next] > dist[now] + nextcost) {
                dist[next] = dist[now] + nextcost;
                calc.push(next);
            }
        }
    }
    std::vector<int> out;
    for (int i = 0; i < q; i++) {
        int x, y;
        std::cin >> x >> y;
        x--;
        y--;
        out.pb(dist[x] + dist[y]);
    }
    rep(i, q)
    {
        cout << out[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 11248
x1, x2, x3, x4, x5 = map(int, input().split())

if x1 == 0:
  print(1)
elif x2 == 0:
  print(2)
elif x3 == 0:
  print(3)
elif x4 == 0:
  print(4)
elif x5 == 0:
  print(5)

Measured memory_bytes: 9172
#include<stdio.h>
#include<limits.h>

int MatrixChainOrder(int P[], int n){
  int i,j,k,l,q;
  int M[n+1][n+1];
  for(i=1;i<=n;i++) M[i][i]=0;
  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j=i+l-1;
      M[i][j]=INT_MAX;
      for(k=i;k<=j-1;k++){
	q=M[i][k]+M[k+1][j]+P[i-1]*P[k]*P[j];
	M[i][j]=min(M[i][j],q);
      }
    }
  }
  return M[1][n];
}

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


main(){
  int i,j,n;
  int P[10000];
  int *p;

  p=P;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d %d",&P[2*i],&P[2*i+1]);
  for(i=1;i<2*n;i++){
    if(P[i]==P[i+1]){
      for(j=i+1;j<2*n;j++)P[j]=P[j+1];
    }
  }
  printf("%d\n",MatrixChainOrder(P,n));
  return 0;
}

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

int main(){

	int n, k;
	cin >> k >> n;
	
	
	int maxd = 0;
	
	int old;
	cin >> old;
	int temp;
	int first = old;
	maxd = old;
	
	for (int i = 1; i < n; i++){
		cin >> temp;
		maxd = max(maxd, temp - old);
		old = temp;
	}
		
	maxd = max(maxd, (k - temp) + first);
	
	cout << (k - maxd) << endl;







	return 0;
}


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

using namespace std;

int main()
{
	long long n, k;
	cin >> n >> k;

	vector<int> a(n);
	for(long long i=0;i<n;i++){
		cin >> a[i];
		a[i]-=1;
	}

	// 探索準備
	int select=0;              // 探索開始場所
	vector<bool> check(n,false);
	int loopcnt=0;
	int start=-1;
	for(long long i=1;i<=k;i++){
		// cout << select+1 << " ";
		if(start != -1){
			loopcnt++;
			if(start==select){
				// cout << endl;
				k=(k-i)%loopcnt+i;
			}
		}
		if(start == -1 && check[select]) start=select;
		check[select] = true;
		select = a[select];
	}
	// cout << endl;
	cout << select+1 << endl;
}

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

int main(){
  int N = 0;
  cin >> N;
  
  vector<char> S(N);
  for(int i = 0; i < N; i++){
    cin >> S.at(i);
  }
  
  for(int i = 0; i < N; i++){
    switch(S.at(i)){
      case 'P' : continue;
      case 'W' : continue;
      case 'G' : continue;
      case 'Y' : cout << "Four" << endl; return 0;
    }
  }
    cout << "Three" << endl; 
}

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

int main()
{
	int num1, num2, num3;

	cin >> num1 >> num2 >> num3;

	if ((num1 + num2 + num3) <= 21)cout << "win";
	else if ((num1 + num2 + num3) > 21)cout << "bust";

	cout << endl;

	return 0;
}

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

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ll> point;
#define F first
#define S second



int main()
{
	#ifdef DGC
		//freopen("a.in", "r", stdin);
		//freopen("a.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	int a, b;
	cin >> a >> b;
	for (int i = 10*b; i < 10*(b+1); ++i)
		if (i * 8 / 100 == a && i * 10 / 100 == b)
		{
			cout << i << "\n";
			return 0;
		}
	cout << "-1\n";

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define ff first;
#define ss second;
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define lli long long int
#define INF 1000000000
#define endl '\n'
const double pi = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
using namespace std;
	
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a;
	cin >> a;
	int sum = a+a*a+a*a*a;
	cout << sum << endl;
	return 0;
}



Measured memory_bytes: 3644
class UnionFind(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, x_zahyou, y_zahyou,parent=None, value=None):
        self.group_id_ = group_id
        self.x_zahyou = x_zahyou
        self.y_zahyou = y_zahyou
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.x_zahyou += unite_root.x_zahyou
                root.y_zahyou += unite_root.y_zahyou
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.x_zahyou+= root.x_zahyou 
                unite_root.y_zahyou+= root.y_zahyou
                
N = int(input())
X = []
Y = []
node_list = []
for i in range(N):
  x, y = map(int,input().split())
  X += [[i,x]]
  Y += [[i,y]]
  node_list += [UnionFind(i,[x],[y])]
X.sort(key=lambda x: x[1])
Y.sort(key=lambda x: x[1])
for i in range(N-1):
  if X[i][1] == X[i+1][1] :
    node_list[X[i][0]].unite(node_list[X[i+1][0]])
  if Y[i][1] == Y[i+1][1] :
    node_list[Y[i][0]].unite(node_list[Y[i+1][0]])
    
chouten = 0
for i in range(N):
  if node_list[i].is_root():
    chouten += len(set(node_list[i].x_zahyou)) * len(set(node_list[i].y_zahyou))
    
print(chouten - N)

Measured memory_bytes: 142852
E = 10**-10
while(1):
    try:
        xa,ya,xb,yb,xc,yc,xd,yd = [float(i) for i in input().split()]
        x1 = xb-xa
        y1 = yb-ya
        x2 = xd-xc
        y2 = yd-yc
        inner = x1*x2+y1*y2
        if abs(inner) < E:
            print("YES")
        else:
            print("NO")
    except EOFError:
        break


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

using Lint=long long;

vector<int> mul(vector<int>& a,vector<int>& b)
{
   const int N=a.size();
   vector<int> res(N);
   for(int i=0;i<N;i++) res[i]=b[a[i]];
   return res;
}

vector<int> pow(vector<int>& p,Lint K)
{
   const int N=p.size();
   vector<int> res(N);
   for(int i=0;i<N;i++) res[i]=i;
   while(K>0){
      if(K&1) res=mul(res,p);
      p=mul(p,p); K>>=1;
   }
   return res;
}

int main()
{
   int N; cin>>N;
   vector<Lint> x(N);
   for(int i=0;i<N;i++) cin>>x[i];
   Lint M,K; cin>>M>>K;
   vector<int> a(M);
   for(int i=0;i<M;i++) cin>>a[i],a[i]--;

   const int sz=N-1;
   vector<int> d(sz);
   for(int i=0;i<sz;i++) d[i]=x[i+1]-x[i];
   vector<int> p(sz);
   for(int i=0;i<sz;i++) p[i]=i;
   for(int i=0;i<M;i++){
      swap(p[a[i]-1],p[a[i]]);
   }
   p=pow(p,K);
   for(int i=0;i<sz;i++) x[i+1]=x[i]+d[p[i]];
   for(int i=0;i<N;i++) cout<<x[i]<<endl;
   return 0;
}


Measured memory_bytes: 3292
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli h, w;
lli c[10][10];
lli a[201][201];
int main() {
  cin >> h >> w;
  for (lli j=0; j<=9; ++j)
    for (lli i=0; i<=9; ++i)
      cin >> c[j][i];
  for (lli j=1; j<=h; ++j)
    for (lli i=1; i<=w; ++i)
      cin >> a[j][i];
  for (lli k=0; k<=9; ++k) {
    for (lli i=0; i<=9; ++i) {
      for (lli j=0; j<=9; ++j) {
	c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
      }
    }
  }
  lli ans = 0;
  for (lli j=1; j<=h; ++j)
    for (lli i=1; i<=w; ++i)
      if (a[j][i] >= 0) ans += c[a[j][i]][1];
  cout << ans << endl;
  return 0;
}



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

int main()
{
    string s,t,u;
    cin >> s >> t >> u;
    
    s[0] -= 32;
    t[0] -= 32;
    u[0] -= 32;
    
    cout << s[0] << t[0] << u[0] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}


int V[55];
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> V[i];
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; i + j <= min(k, n); j++) {
            vector<int> v;
            for (int x = 1; x <= i; x++) v.push_back(V[x]);
            for (int x = 0; x < j; x++) v.push_back(V[n - x]);
            sort(v.rbegin(), v.rend());
            int k2 = k - i - j;
            while (k2 > 0 && !v.empty() && v.back() < 0) {
                v.pop_back();
                k2--;
            }
            int sum = 0;
            for (int x : v) sum += x;
            ans = max(ans, sum);
        }
    }
    cout << ans;
}


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

int n, s, m;

void sm(int i, int j, int r) {
	if (i == 10) {
		if (j == n && r == s)
			m++;
	}
	else {
		sm(i + 1, j + 1, r + i);
		sm(i + 1, j, r);
	}
}

int main()
{	
	cin >> n >> s;

	while (n > 0 || s > 0) {
		m = 0;

		sm(0, 0, 0);
		cout << m << endl;

		cin >> n >> s;
	}

	return 0;
}



Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
int N,M;
vector <bool> WFS(int t, vector <vector <pair<long long,long long>>> edge);
int main()
{
    cin >> N >> M;
    vector <vector <pair<long long,long long>>> edge(N+1);
    long long a,b,c;
    vector <vector<long long>> opt(N+1,vector<long long> (N+1));
    for (int i=0;i<M;i++)
    {
        cin >> a >> b >> c;
        edge[b].push_back(make_pair(a,-c));
    } 
    for (int i=1;i<N+1;i++) opt[0][i]=LONG_MAX/3*2;
    opt[0][1]=0;
    for (int i=1;i<N+1;i++)
    {
        for (int v=1;v<N+1;v++)
        {
            opt[i][v]=opt[i-1][v];
            for (int u=0;u<edge[v].size();u++)
            {
                opt[i][v]=min({opt[i-1][v],opt[i-1][edge[v][u].first]+edge[v][u].second,opt[i][v]});
            }
        }
    }
    vector <bool> visit;
    visit=WFS(N,edge);
    bool can=true;
    for (int i=1;i<N+1;i++)
    {
        if (visit[i])
        {
            if (opt[N][i]!=opt[N-1][i]) 
            {
                cout << "inf" << endl;
                can=false;
                break;
            } 
        }
    }
    if (can) cout << -opt[N][N] << endl;
return 0;
}

vector <bool> WFS(int t, vector <vector <pair<long long,long long>>> edge)
{
    vector <bool> visit(N+1);
    visit[0]=true;
    vector <int> que;
    que.push_back(t);
    for (int i=0;i<N+1;i++)
    {
        visit[i]=false;
    }
    int v;
    while (!que.empty())
    {
        v=que.front();
        que.erase(que.begin());
        for (int u=0;u<edge[v].size();u++)
        {
            if (!visit[edge[v][u].first])
            {
                visit[edge[v][u].first]=true;
                que.push_back(edge[v][u].first);
            }
        }
    }
return visit;
}

Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N;
  int K;
  cin>>N;
  cin>>K;
  set<int> s;
  for(int i = 1;i <= N;i++){
    s.insert(i);
  }
  for(int i = 1;i <= K;i++){
    int num;
    cin>>num;
    for(int i = 1;i <= num;i++){
      int a;
      cin>>a;
      if(s.lower_bound(a) != s.end() && *s.lower_bound(a) == a){
        s.erase(a);
      }
    } 
  }
  cout<<s.size()<<'\n';
}

Measured memory_bytes: 3664
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<stack>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define N 300010
namespace uf{
	ll dat[N];
	stack<P> s;
	void init(){
		rep(i,N)dat[i]=-1;
		while(!s.empty())s.pop();
	}
	void confirm(){
		while(!s.empty())s.pop();
	}
	ll find(ll x){
		return (dat[x]<0?x:find(dat[x]));
	}
	void unite(ll a,ll b){
		a=find(a),b=find(b);
		if(a==b)return;
		if(-dat[a]<-dat[b])swap(a,b);
		s.push(make_pair(a,dat[a]));
		s.push(make_pair(b,dat[b]));
		dat[a]+=dat[b];
		dat[b]=a;
	}
	bool same(ll a,ll b){
		return find(a)==find(b);
	}
	void rollback(){
		while(!s.empty()){
			dat[s.top().first]=s.top().second;
			s.pop();
		}
	}
};

int main(){
	ll n,q;
	cin>>n>>q;
	uf::init();
	rep(u,q){
		rep(e,5+rand()%3){
			ll x=rand()%n,y=rand()%n;
			uf::unite(x,y);
		}
		uf::rollback();
		bool com;
		ll x,y;
		cin>>com>>x>>y;
		if(com==0){
			uf::unite(x,y);
		}
		else{
			cout<<uf::same(x,y)<<endl;
		}
		uf::confirm();
	}
}



Measured memory_bytes: 5464
n,k=map(int,input().split())
s=input()
A=[]
now=1
cnt=0
for i in range(n):
    if int(s[i])==now:
        cnt+=1
    else:
        now^=1
        A.append(cnt)
        cnt=1
A.append(cnt)
if len(A)%2==0:
    A.append(0)



bk=2*k+1
ans=sum(A[0:bk])
res=ans
left=0
right=bk
while right+2<=len(A):
    res-=A[left]
    res-=A[left+1]
    left+=2    
    res+=A[right]
    res+=A[right+1]
    right+=2
    ans=max(res,ans)
print(ans)
    



Measured memory_bytes: 79136
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long n = sc.nextLong();
    long m = sc.nextLong();
    Queue<Long> queue = new PriorityQueue<>(Collections.reverseOrder());
    for (int i = 0; i < n; i++) queue.add(sc.nextLong());
    for (int i = 0; i < m; i++) queue.add(queue.poll() / 2);
    long result = queue.stream().reduce((a, b) -> a + b).get();
    System.out.println(result);
  }
}

Measured memory_bytes: 61416
var oturi=[];
for(var i=0;i<=500;i++){
   var sum=i;
   var cnt=0;
   while(sum>=500){sum-=500;cnt++;}
   while(sum>=100){sum-=100;cnt++;}
   while(sum>=50){sum-=50;cnt++;}
   while(sum>=10){sum-=10;cnt++;}
   while(sum>=5){sum-=5;cnt++;}
   while(sum>=1){sum-=1;cnt++;}
   oturi[i]=cnt;
}

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
while(true){
   var str=arr.shift();
   if(str=="0 0 0 0 0 0 0")break;
   var ary=str.split(" ").map(Number);
   var P=ary[0];
   var min=Infinity;
   for(var i=P;i<P+500;i++){
      (function(p,a,b,c,d,e,f){
         var sum=i;
         var cnt=0;
         while(sum>=500 && f>0){sum-=500;f--;cnt++;}
         while(sum>=100 && e>0){sum-=100;e--;cnt++;}
         while(sum>=50 && d>0){sum-=50;d--;cnt++;}
         while(sum>=10 && c>0){sum-=10;c--;cnt++;}
         while(sum>=5 && b>0){sum-=5;b--;cnt++;}
         while(sum>=1 && a>0){sum-=1;a--;cnt++;}
         if(sum==0)min=Math.min(cnt+oturi[i-P],min);
      }).apply(null,ary);
   }
   console.log(min);
}

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

using namespace std;

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	while(a > 0 && c > 0) {
		c -= b;

		if(c <= 0) {
			break;
		}

		a -= d;
	}

	if(a <= 0) {
		cout << "No" << '\n';
	} else {
		cout << "Yes" << '\n';
	}

	return 0;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  int x;
  cin >> x;
  if (x >= 30) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}

Measured memory_bytes: 3648
n,m,x = map(int, input().split())
a = list(map(int, input().split()))
s = x
cost = 0
while s!=0:
    s-=1
    if s in a:
        cost+=1
ans = cost
cost = 0
s = x
while s!=n:
    s+=1
    if s in a:
        cost+=1 
ans = min(ans,cost)
print(ans)

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

typedef pair<int,int>P;
const int inf=100000000;

char maze[1000][1000];
int d[1000][1000];
int N,W,H;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int step=0;
P a,b,cheese[10];

int bfs(P a,P b)
{
	queue<P> que;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			d[i][j]=inf;
		}
	}
	que.push(a); 
	d[a.first][a.second]=0;
	while(que.size())
	{
		P p=que.front();
		que.pop();
		if(p.first==b.first&&p.second==b.second)
		{
			break;
		}
		for(int i=0;i<4;i++)
		{
			int nx=p.first+dx[i];
			int ny=p.second+dy[i];
			if(nx>=0&&nx<H&&ny>=0&&ny<W&&maze[nx][ny]!='X'&&d[nx][ny]==inf)
			{
				que.push(P(nx,ny));
				d[nx][ny]=d[p.first][p.second]+1;
			}
		}
	}
	return d[b.first][b.second];
}

int main()
{
	cin>>H>>W>>N;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			cin>>maze[i][j];
			if(maze[i][j]>='0'&&maze[i][j]<='9')
			{
				int c=maze[i][j]-'0';
				cheese[c].first=i;
				cheese[c].second=j;
			}
			else if(maze[i][j]=='S')
			{
				a.first=i;
				a.second=j;
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		b.first=cheese[i].first;
		b.second=cheese[i].second;
		step+=bfs(a,b);
		a.first=b.first;
		a.second=b.second;
	}
	
	cout<<step<<endl;
}


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

int main(){
	int n;
	cin>>n;
	if(n>0 && n<1000){
		cout<<"ABC";
	}
	else{
		cout<<"ABD";
	}
}

Measured memory_bytes: 256
t,x,y,z=0,0,0,0
while True:
    try:
        a=sorted(list(map(int,raw_input().split())))
        if a[0] + a[1] > a[2]:
            t+=1
            if a[0]**2 + a[1]**2 == a[2]**2:
                x+=1
            elif a[0]**2 + a[1]**2 > a[2]**2:
                y+=1
            else:
                z+=1
        else:
            print t, x, y, z
            quit()
    except ValueError:
        break
print t, x, y, z


Measured memory_bytes: 4660
#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>
#include <cmath>

int N;
long K;

std::map<int, long> table;

int main()
{
  std::cin >> N >> K;
  for (int i=0; i<N; i++) {
    int a, b;
    std::cin >> a >> b;
    auto iter = table.find(a);
    if (iter==table.end()) table.emplace_hint(iter, a, b);
    else iter->second += b;
  }
  for (auto iter=table.begin(); iter!=table.end(); iter++) {
    K -= iter->second;
    if (K<=0) {
      std::cout << iter->first;
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 4224
#pragma once

#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;

#define rep(a,n) for(int a = 0;a < n;a++)
#define repi(a,b,n) for(int a = b;a < n;a++)

const ull mod = 1000000007;

struct workspace {

};

int main(void)
{
	ll n, a, b;
	cin >> n >> a >> b;
	ll dist = abs(b - a);
	if (dist % 2 == 0) {
		cout << dist / 2 << endl;
	}
	else {
		auto m1 = n - max(a, b) + 1;
		auto n1 = (n - (min(a, b) + m1)) / 2;
		auto c2 = m1 + n1;

		auto m2 = min(a, b) - 1 + 1;
		auto n2 = (max(a, b) - m2 - 1) / 2;
		auto c3 = m2 + n2;
		cout << min(c3, c2) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define loop(i, r, n) for (int i = (r); i < (n); i++)
#define pb push_back
#define all(in) in.begin(),in.end()

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

using ll = long long;
using ull = unsigned long long;
using namespace std;
using namespace atcoder;
// cout << fixed << setprecision(10）<<  << endl;

vector<pair<ll,ll>> prime(ll n) {
    vector<pair<ll,ll>> res;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i != 0) continue;
        ll count = 0;
        while (n % i == 0) { count++; n /= i; }
        res.push_back(make_pair(i,count));
    }
    if(n != 1) res.push_back(make_pair(n,1));
    return res;
}

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

ll GCD(ll a, ll b){
    ll s = a, t = b;
    while(s % t) { s %= t; swap(s,t); }
    return t;
}

const ll INF = 1ll<<60;

ll extGCD(ll a, ll b, ll &x, ll &y) {
    x = 1, y = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a,b);
        x -= t * y; swap(x,y);
    }
    return a;
}

int main(){
    ll n; cin >> n;
    auto p = prime(n * 2ll);
if (n == 1) { cout << 1 << endl; return 0; }
    vector<ll> ans;
    for (int i = 0; i < (int)p.size(); i++) {
        ll div = p[i].first, num = p[i].second;
        ans.push_back(pow(div, num));
    }
    ll res = n - 1ll; n *= 2;
    for(ll i = 0; i < 1<<(ll)ans.size(); i++) {
        ll c1 = 1ll;
        for (ll j = 0; j < (int)ans.size(); j++) {
            if (i & 1ll<<j) c1 *= ans[j];
        }
      if (c1 == 1ll || c1 == n) continue; ll c2 = n / c1;
      if (c1 + 1 == c2) { cout << c1 << endl;
                         return 0;
                        }
        ll x, y;
        extGCD(c2, -c1, x, y);
        ll count = c2 * x;
        count = (count % n + n) % n;
      if (count == 0) continue;
        chmin(res, count);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3672
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  string S;
  cin>>S;
  bool up = false;
  if(S[0]=='<') up = true;
  vector<ll> arr;
  arr.push_back(0);
  for(ll i=1;i<S.size();++i) {
    if(up && S[i]=='>') {
      up = false;
      arr.push_back(i);
    }
    else if(!up && S[i]=='<') {
      up = true;
      arr.push_back(i);
    }
  }
  arr.push_back(S.size());
  ll ans = 0;
  ll num;
  if(S[0]=='<') {
    for(ll i=1;i<arr.size();++i) {
      if(i%2==0) { // tani
        num = max(arr[i]-arr[i-1], arr[i-1]-arr[i-2]);
        if(num==arr[i]-arr[i-1]) ans += num*(num+1)/2;
        else ans += (arr[i]-arr[i-1])*(arr[i]-arr[i-1]+1)/2 - (arr[i]-arr[i-1])+num;
      }
      else { // yama
        if(i==arr.size()-1) {
          ans += (arr[i]-arr[i-1])*(arr[i]-arr[i-1]+1)/2;
        }
        else {
          num = max(arr[i+1]-arr[i], arr[i]-arr[i-1]);
          if(num==arr[i]-arr[i-1]) ans += num*(num+1)/2-num;
          else ans += (arr[i]-arr[i-1])*(arr[i]-arr[i-1]+1)/2-(arr[i]-arr[i-1]);
        }
      }
    }
  }
  else {
    for(ll i=1;i<arr.size();++i) {
      if(i%2!=0) { // tani
        num = max(arr[i]-arr[i-1], arr[i-1]-arr[i-2]);
        if(num==arr[i]-arr[i-1]) ans += num*(num+1)/2;
        else ans += (arr[i]-arr[i-1])*(arr[i]-arr[i-1]+1)/2 - (arr[i]-arr[i-1])+num;
      }
      else { // yama
        if(i==arr.size()-1) {
          ans += (arr[i]-arr[i-1])*(arr[i]-arr[i-1]+1)/2;
        }
        else {
          num = max(arr[i+1]-arr[i], arr[i]-arr[i-1]);
          if(num==arr[i]-arr[i-1]) ans += num*(num+1)/2-num;
          else ans += (arr[i]-arr[i-1])*(arr[i]-arr[i-1]+1)/2-(arr[i]-arr[i-1]);
        }
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 6132
N, K = map(int, input().split())
List = list(map(int, input().split()))


remain_monster = N - K
if remain_monster <= 0:
    monsterHP = 0

else:
    new_list = sorted(List, reverse=True)

    monsterHP = sum(new_list[-remain_monster:])

print(monsterHP)



Measured memory_bytes: 26180
#include <stdio.h>

bool containCap(char *s);
bool containNum(char *s);
bool containSml(char *s);
int strlen(char *s);
bool isValid(char *password);

int main(){
    char s[30];
    
    scanf("%s", s);
    printf("%s\n", isValid(s) ? "VALID" : "INVALID");
    
    return 0;
}

bool containCap(char *s){
    for (char *p=s; *p != '\0'; p++){
        if ('A' <= *p && *p <= 'Z') return true;
    }
    return false;
}
bool containNum(char *s){
    for (char *p=s; *p != '\0'; p++){
        if ('0' <= *p && *p <= '9') return true;
    }
    return false;
}
bool containSml(char *s){
    for (char *p=s; *p != '\0'; p++){
        if ('a' <= *p && *p <= 'z') return true;
    }
    return false;
}
int strlen(char *s){
    int i=0;
    for (char *p=s; *p != '\0'; p++){
        i++;
    }
    return i;
}
bool isValid(char *password){
    return containCap(password) &&
            containSml(password) &&
            containNum(password) &&
            (strlen(password) >= 6);
}

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

int d[15][15];
int dp[1<<15][15];

int main(){
    int N, M; cin >> N >> M;
    int INF=pow(10,9);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            d[i][j]=INF;
        }
    }
    for(int i=0; i<M; i++){
        int s, t, di;
        cin >> s >> t >> di;
        d[s][t]=di;
    }
    for(int i=0; i< 1<<15; i++){
        for(int j=0; j<15; j++){
            dp[i][j]=INF;
        }
    }
    dp[(1<<N)-1][0]=0;
    for(int S=(1<<N)-2; S>=0; S--){
        for(int v=0; v<N; v++){
//            if( ! (1<<v &S) ) continue;
            for(int u=0; u<N; u++){
                if(!(S>>u &1)){
                    dp[S][v]=min(dp[S][v], dp[S|1<<u][u]+d[v][u]);
                }
            }
        }
    }
    if(dp[0][0]<INF){
    cout << dp[0][0] << endl;
    }
    else cout << -1 << endl;
}


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

double zyou(int x){
double ans=1;
  rep(i,x){
ans *=2;
}
  return ans;
}

int main(){
int n;
  cin >>n;
  vector<double> a(n);
  rep(i,n) cin >>a.at(i);
  sort(a.begin(),a.end());
  double x = a.at(0)+a.at(1);
  double x2 = zyou(n-1);
  double ans = x/x2;
  
  for(int i =2;i<n;i++){
  double y =a.at(i)/zyou(n-i);
    ans += y;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdint.h>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

typedef __int128_t ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-12;
static const double PI = acos(-1.0);
static const ll MOD = 1000000007;

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define DEBUG(x) cout << #x << ": " << x << endl

ll solve(long long N, std::vector<long long> A) {
  std::vector<ll> B(N);
  if (N == 0) {
    if (A[0] == 1) {
      return 1;
    } else {
      return -1;
    }
  }
  if (A[0] != 0) {
    return -1;
  }
  ll max = 1;
  REP(i, 13) { max *= 10; }
  ll cur = 1;
  FOR(i, 1, N) {
    cur *= 2;
    cur -= A[i];
    if (cur < 0) {
      return -1;
    }
    B[i] = cur;
    cur = min(cur, max);
  }
  cur *= 2;
  if (cur < A[N]) {
    return -1;
  }
  ll ans = 1 + A[N];
  ll cur1 = A[N];
  for (ll i = N - 1; i > 0; i--) {
    ans += A[i] + min(cur1, B[i]);
    cur1 += A[i];
  }
  return ans;
}

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


Measured memory_bytes: 5632
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <stack>
#include <queue>

typedef long long ll;

using namespace std;

int main(void){
	int n; cin >> n;
	int v[21], c[21];
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	for(int i=0; i<n; i++){
		cin >> c[i];
	}

	int val=0, cost=0;
	for(int i=0; i<n; i++){
		if(v[i] > c[i]){
			val += v[i];
			cost += c[i];
		}
	}

	cout << val - cost << endl;

	return 0;
}

Measured memory_bytes: 256