akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

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

    int x = n / 500;

    long long int points = (long long) (x*1000);
    int rem = n - (x*500);

    points += ((rem/5)*5);

    cout << points << endl;

    return 0;
}


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

int main() {

  int n,x,t,a,ans;
	cin >>  n>>  x>>  t;
	ans=n/x;
	a=n%x;
	ans=ans*t;
	
	if(a==0){
	
	cout << ans << endl;
	}
	else{
	ans=ans+t;
	cout << ans << endl;
	}

}

Measured memory_bytes: 3620
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <utility>
#include <string>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> ab;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if (ab.size() == 0 || ab.back().second != a) {
            ab.emplace_back(b, a);
        }
    }
    sort(ab.begin(), ab.end());
    int ans = 0;
    int last = 0;
    for (auto&& e : ab) {
        if (e.second >= last) {
            ans++;
            last = e.first;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1400
/*Bismillahir Rahmanir Rahim*/
#include<bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf

#define sf1(a)			scanf("%d",&a);
#define sf2(a,b)		scanf("%d%d",&a,&b);

#define ll				long long

#define fin             freopen("input.txt","r",stdin);
#define fout            freopen("output.txt","w",stdout);

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin >> t;
	string a,b;
	cin >> a >> b;
	for(int i=0;i<t;i++){
		cout << a[i] << b[i];
	}
	cout << endl;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
//#include<ext/pb_ds/assoc_container.hpp>
#pragma comment(linker, "/STACK:16000000")
//#define map gp_hash_table
#define PI 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const long long inf2=0x3f3f3f3f3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
vector<int> g[2222],g2[2222];
int n;
pair<int,int> a[2002];
vector<vector<int> > vec;
bool used[2002];
void dfs(int x){
	used[x]=true;
	for(int i=0;i<g[x].size();i++){
		if(used[g[x][i]])continue;
		g2[x].push_back(g[x][i]);
		dfs(g[x][i]);
	}
}
priority_queue<int>q;
signed main(){
	vec.clear();
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].first,a[i].second=i;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(__gcd(a[i].first,a[j].first)!=1){
		g[i].push_back(j);
	}
	for(int i=1;i<=n;i++)if(!used[i]){
		dfs(i);
		q.push(i);
	}
	memset(used,false,sizeof(used));
	while(q.size()){
		int x=q.top();q.pop();
		used[x]=false;
		for(int i=0;i<g2[x].size();i++)q.push(g2[x][i]);
		cout<<a[x].first<<" ";
	}
	return 0;
}


Measured memory_bytes: 27776
N,L=map(int,input().split())
list1=[]
list2=[]
for i in range(1,N+1):
    list1.append(N*L+(N-1)*N/2-L+1-i)
    list2.append(abs(N*L+N*(N-1)/2-((N-1)*(L+N/2)+1-i)))
print(int(list1[list2.index(min(list2))]))

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;

namespace AIZU {
	class Program {
		static int cin() { return cin(-1); }
		static int cin(int D) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return int.Parse(s);
		}
		static int[] cins(char spliter) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return new int[] { };
			string[] ss = s.Split(spliter);
			int[] Res = new int[ss.Length];
			for (int i = 0; i < ss.Length; i++)
				Res[i] = int.Parse(ss[i]);
			return Res;
		}
		static int[] cins() { return cins(' '); }
		static void print(object j) { Console.WriteLine(j.ToString()); }
		static void print(string j) { Console.WriteLine(j); }
		
		static void Main(string[] args) {
			List<int>[] Point = new List<int>[100];
			int[] I;
			while (true) {
				for (int iop = 0; iop < 100; iop++)
					Point[iop] = new List<int>();
				while (true) {
					I = cins();
					if (I.Length == 0)
						return;
					if (I[0] == 0 && I[1] == 0)
						break;
					Point[I[0]-1].Add(I[1]-1);
					Point[I[1]-1].Add(I[0]-1);

				}
				bool res;
				res = Point.Take(2).All(L => L.Count % 2 == 1)
					&&Point.Skip(2).All(L => L.Count % 2 == 0);
				print(res ? "OK" : "NG");
			}
		}
	}
}

Measured memory_bytes: 9336
#include<cstdio>
#include<iostream>
#include <algorithm>
using namespace std;

int main() {
	int n, a;
	cin >> n;
	cin >> a;
	if (n % 500 == 0) {
		cout << "Yes" << endl;
	}
	else {
		if (n % 500 - a <= 0) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
const double pi = acos(-1);
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
// bool operator<(const pair<int, int> &a, const pair<int, int> &b)
// {
//     if (a.first == b.first)
//         return a.second < b.second;
//     return a.first < b.first;
// };

/*unsigned int xor128(void)
{
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
unsigned int xor128rnd(unsigned int m)
{
    return xor128() % m;
}*/

bool operator<(const pair<ll, ll> &a, const pair<ll, ll> &b)
{

    if (a.first == b.first)
        return a.second < b.second;

    return a.first < b.first;
}
int arr[3010];
ll dp[3010][3010];

ll f(int l, int r)
{
    if (r < l)
        return 0;

    ll memo = dp[l][r];
    if (memo != 100000000000)
        return memo;

    return dp[l][r] = max(arr[l] - f(l + 1, r), arr[r] - f(l, r - 1));
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(10);
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i];
    }

    for (int i = 0; i < 3010; ++i)
    {
        for (int j = 0; j < 3010; ++j)
        {
            dp[i][j] = 100000000000;
        }
    }
    cout << f(0, N - 1) << endl;
    return 0;
}


Measured memory_bytes: 71296
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        string s;
        cin >> s;
        int n = s.length();
        string s1 = s.substr(0, n / 2);
        string s2 = s.substr(n / 2 + 1);
        string s3 = s1, s4 = s2;
        reverse(all(s3));
        reverse(all(s4));
        if(s1 == s2 and s1 == s3 and s4 == s2){
            cout << "Yes\n";
        }else{
            cout << "No\n";
        }
    }
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
using Graph = vector<vector<int>>;
const unsigned long long mod = 1e9 + 7;
const long long INF = 1LL<<60;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int r;	cin>>r;
	cout<<r*r<<endl;


    return 0;
}




Measured memory_bytes: 256
# -*- coding: utf-8 -*-

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def factorize(a):
    ret = set()
    i = 2
    while i * i < a:
        if a % i != 0:
            i += 1
        else:
            while a % i == 0:
                a //= i
                ret.add(i)
            i += 1
    if a != 1:
        ret.add(a)
    return ret

def main():
    A, B = map(int,input().split())
    ABgcd = gcd(A, B)
    ABfactor = factorize(ABgcd)
    Ans = len(ABfactor) + 1
    print(Ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mod_) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod_;
		}
		x = x * x % mod_;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}
/*--------Library Zone!--------*/

int n, a[114514];
int sum[114514];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	int ans = 0, k = kai(n);
	rep(i, n) {
		if (i)sum[i] += sum[i - 1];
		sum[i] += k * mod_pow(i + 1, mod - 2, mod);
		sum[i] %= mod;
	}
	rep(i, n) {
		ans += a[i] * sum[i] + a[i] * ((sum[n - i - 1] - sum[0] + mod) % mod);
		ans %= mod;
	}
	cout << ans << endl;
}

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] aa = new int[3];
        aa[0] = Integer.parseInt(sc.next());
        aa[1] = Integer.parseInt(sc.next());
        aa[2] = Integer.parseInt(sc.next());
        int cnt = 0;
        while (true) {
            Arrays.sort(aa);
            if (aa[0] == aa[1] && aa[1] == aa[2]) {
                break;
            }
            cnt++;
            if (aa[0] == aa[1]) {
                aa[0]++;
                aa[1]++;
            } else {
                aa[0] += 2;
            }
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 21972
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <iterator>
#include <cmath>
#include <deque>
using namespace std;

int main()
{
    {
        if (fopen("input.txt", "r")) {
            freopen("input.txt", "r", stdin);
            freopen("output.txt", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    }
    int x, y;
    cin >> x >> y;
    int ans = 0;
    switch (x) {
    case 1:
        ans += 300000;
        break;
    case 2:
        ans += 200000;
        break;
    case 3:
        ans += 100000;
        break;
    }
    switch (y) {
    case 1:
        ans += 300000;
        break;
    case 2:
        ans += 200000;
        break;
    case 3:
        ans += 100000;
        break;
    }
    if (x == 1 && y == 1)
        ans += 400000;
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
N,A,B=map(x->parse(Int,x),split(readline()))
v=reverse(sort(map(x->parse(Int,x),split(readline()))))
println(sum(v[1:A])/A)
if v[1]!=v[A]
	X=Y=0
	for i=1:N
		if v[i]==v[A]
			X+=1
			Y+=i<=A
		end
	end
	println(binomial(X,Y))
else
	X=0
	for i=1:N
		if v[i]==v[A]
			X+=1
		end
	end
	println(sum(binomial(X,i) for i=A:B))
end


Measured memory_bytes: 117204
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

result = 0
prev = -1
for i in A:
  result += B[i-1]
  if prev == i-1 and i -2 >= 0:
    result += C[i-2]
  prev = i
  
print(result)

Measured memory_bytes: 3064
//Name: Matsuzaki Number
//Level: 2
//Category: 素数
//Note:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_PRIME = 200000;
vector<int> primes;
bool is_prime[MAX_PRIME+1];

void init() {
    fill_n(is_prime, MAX_PRIME+1, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= MAX_PRIME; ++i) {
        if(is_prime[i]) {
            primes.push_back(i);
            for(long long j = (long long)i*i; j <= MAX_PRIME; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

bool solve() {
    int N, P;
    cin >> N >> P;
    if(N == -1 && P == -1) return false;

    vector<int>::iterator first = upper_bound(primes.begin(), primes.end(), N);
    vector<int> nums;
    const int start = distance(primes.begin(), first);
    for(int i = start; i < start+100; ++i) {
        for(int j = i; j < start+100; ++j) {
            nums.push_back(primes[i]+primes[j]);
        }
    }
    sort(nums.begin(), nums.end());
    cout << nums[P-1] << endl;
    return true;
}

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

    init();
    for(int case_num = 1; solve(); ++case_num) ;
    return 0;
}

Measured memory_bytes: 1556
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}
const int MOD = 1000000007;




int main() {
    string a;
    cin >> a;
    string ans;
    for(int i = 0;i < a.length();i++){
        if(a[i] == '0'){
            ans += '0';
        }else if(a[i] == '1'){
            ans += '1';
        }else{
            if(ans.length() > 0){
                ans = ans.substr(0,ans.length()-1);
            }
        }
    }
    cout << ans;
}



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

using namespace std;

struct pt
{
  int x, y;

  pt operator - ( pt & p ) const 
  {
    return { x - p.x, y - p.y };
  }

};

long long dot( pt p, pt q )
{
  return p.x * q.x + p.y * q.y;
}

long long cross( pt p, pt q )
{
  return p.x * q.y - p.y * q.x;
}

long long orient( pt a, pt b, pt c )
{
  return cross( b - a, c - a );
}

enum {IN,OUT,ON};

int point_in_polygon( vector< pt > &pol, pt p )
{
  int wn = 0;
  for( int i = 0, n = pol.size(); i < n; ++ i )
  {
    long long c = orient( p, pol[i], pol[(i+1)%n] );
    if( c == 0 && dot( pol[i] - p, pol[(i+1)%n] - p ) <= 0 ) return ON; 
    if( c > 0 && pol[i].y <= p.y && pol[(i+1)%n].y > p.y ) ++ wn;
    if( c < 0 && pol[(i+1)%n].y <= p.y && pol[i].y > p.y ) --wn;
  }
  return wn ? IN : OUT;
}

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

  vector< pt > pol( n );
  for( auto &p : pol )
    scanf("%d %d", &p.x, &p.y );

  int q;
  scanf("%d", &q );
  while( q-- )
  {
    pt p;
    scanf("%d %d", &p.x, &p.y );

    int r = point_in_polygon( pol, p );
    if( r == IN ) puts("2");
    if( r == ON ) puts("1");
    if( r == OUT ) puts("0");
  }
  return 0;
}


Measured memory_bytes: 3108
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#define rep(i, n) for(int i = 0; i < n; i ++)
#define ALL(T) T.begin(), T.end()
#define mp make_pair
#define pb push_back
#define MEMSET(v, h) memset((v), h, sizeof(v))

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

const int INF = 1 << 24;

int main(void){
    bool l[126] = {0};
	int i;
	char c;
	while(1){
		c = getchar();
		if(c=='.')return 0;
		i = 0;
		do{
			if(c=='('||c=='[') l[i++] = c=='[';
			if((c==')'||c==']') && (l[--i] == (c==')'))){i=-10; break;}
		}while( (c=getchar())!='.' && i>=0 &&i<126);
		if(c!='.') while(getchar()!='.');
		getchar();
		printf(i==0?"yes\n":"no\n");
	}
    return 0;
}

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

int main() {
	ios_base::sync_with_stdio( false );

	int N, K;
	cin >> N >> K;
	string S;
	cin >> S;
	S[K-1] += 'a' - 'A';
	cout << S << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    string s, t; cin >> s >> t;
    int n_s = s.size(), n_t = t.size();
    int ans = inf;
    for (int i = 0; i <= n_s - n_t; i++) {
        int diff = 0;
        rep(j,n_t) {
            if (s[i+j] != t[j]) diff++;
        }
        ans = min(ans,diff);
    }
    cout << ans << endl;
}

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

int main(){
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    if (A < B) swap(A, B);
    if (A < C) swap(A, C);
    if (B < C) swap(B, C);
    for (int i = 0; i < K; i ++){
        A *= 2;
    }
    cout << A + B + C << endl;
    
}


Measured memory_bytes: 256
import math

A, B, H, M = map(int, input().split())

deg_H = 360*(H+M/60)/12
deg_M = 360*M/60

theta = math.radians(abs(deg_H - deg_M))

ans = B**2 + A**2 - 2*A*B*math.cos(theta)

print(ans**0.5)


Measured memory_bytes: 9488
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n[4];

bool solve() {
    string s = "";
    for (int i = 0; i < 4; i++) s += to_string(n[i]);
    sort(ALL(s));
    return s == "1479";
}

void input() {
    for (int i = 0; i < 4; i++) cin >> n[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    cout << (solve()?"YES":"NO") << endl;
}


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

import sys

input = iter(sys.stdin.read().splitlines()).__next__

W, H, x, y = map(int, input().split())

area = W*H / 2
if x*2 == W and y*2 == H:
   print('%f 1' % (area))
else:
   print('%f 0' % (area))



Measured memory_bytes: 2940
using System;

namespace ITP1_5_D
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int i = 0;
            while (++i <= n) if (Include3(i)) Console.Write(" " + i);
            Console.WriteLine();
        }

        static bool Include3(int x)
        {
            if (x % 3 == 0) return true;
            while (x > 0)
            {
                if (x % 10 == 3) return true;
                x /= 10;
            }
            return false;
        }
    }
}

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

#define     Boost               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define     all(cont)           cont.begin(),cont.end()
#define     rall(cont)          cont.rbegin(),cont.rend()
#define     foreach(cont)       for(auto &val: cont)
#define     dbg(args...)        do {   cerr << #args << "-> " ;  show(args); } while(0); cerr<< endl ;
#define     TS                  template < typename T >
#define     TP                  template < typename F, typename S >
#define     TM                  template<typename T1, typename... T2>
#define     flush               cin.ignore(numeric_limits<streamsize>::max(), '\n')
#define     Case                cout<< "Case "<< ++cs <<": "
#define     PI                  3.1415926535897932384
#define     eps                 1e-9
#define     inf                 LLONG_MIN
#define     INF                 LLONG_MAX
#define     mp                  make_pair
#define     pb                  push_back
#define     ff                  first
#define     ss                  second

typedef     long long                   ll ;
typedef     unsigned long long          ull ;
typedef     pair <int, int>             pii ;

/** Debugging Tool **/
TS void show(const T& v) {    cerr << v << ' ' ;}
TM void show(const T1& first,const T2&... rest){show(first);show(rest...);}
TP ostream& operator<<(ostream& os,const pair<F,S>& p){return os<<"("<<p.ff<<", "<<p.ss<<")";}
TS ostream& operator<<(ostream& os,const vector<T>& v){os << "{"; typename vector< T >::const_iterator it;
    for(it=v.begin();it!=v.end();it++){if( it != v.begin() )os<<", ";os<<*it;}return os<<"}";}
TS ostream& operator<<(ostream& os,const set<T>& v){os<<"[";typename set<T>::const_iterator it;
    for(it=v.begin();it!=v.end();it++){if(it!=v.begin())os<<", ";os<<*it;}return os<<"]";}
TP ostream& operator<<(ostream& os,const map<F,S>& v){os<<"[";typename map<F,S>::const_iterator it;
    for(it=v.begin();it!=v.end();it++){if(it!=v.begin())os<<", ";os<<it->ff<<" = "<<it->ss;}return os<<"]";}
/** Ends **/


void solve(){
    int a,val ;
    cin>> a ;
    int sum = 0 ;
    val = a ;
    for(int i=0; i<3; i++,val*=a)
        sum += val ;
    cout<< sum << endl ;
}


int main()
{
    Boost;

    #ifndef ONLINE_JUDGE
    clock_t tStart = clock();
    freopen("input.txt","r",stdin);    // Read
    freopen("output.txt","w",stdout);  // Write
    #endif

    int t = 1,cs = 0 ;
    //scanf("%d",&t) ;

    while(t--){
        //Case ;
        solve() ;
    }

    #ifndef ONLINE_JUDGE
    fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif

    return 0;
}



Measured memory_bytes: 3608
package main

import (
	"fmt"
	"sort"
	"strconv"
)

var nums map[int]int

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func dfs(s string) {
	if len(s) >= 11 {
		return
	}
	v, _ := strconv.Atoi(s)
	nums[v]++
	for i := 0; i < 10; i++ {
		d := int(s[len(s)-1] - '0')
		if abs(d-i) <= 1 {
			dfs(s + strconv.Itoa(i))
		}
	}
}

func main() {
	var K int
	fmt.Scan(&K)
	nums = make(map[int]int, 0)
	for i := 1; i < 10; i++ {
		dfs(strconv.Itoa(i))
	}
	// fmt.Println(len(nums))
	keys := make([]int, 0)
	for k := range nums {
		keys = append(keys, k)
	}
	sort.Ints(keys)
	// fmt.Println("keys:")
	// fmt.Println(keys[:20])
	fmt.Println(keys[K-1])
}


Measured memory_bytes: 18432
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    string s,t;
    cin >> s >> t;
    int size = s.length();
    int ans = 0;
    rep(i,size){
        if(s[i] != t[i]) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3812
using System;
using System.Collections.Generic;

class unko
{
    static void Main()
    {
        string str;
        List<string> Answers = new List<string>();  //?????£???????????????????????????????????????????´???????????????????

        while((str = Console.ReadLine()) != "-")
        {
            char[] chaan = new char[str.Length];     //????????????????????¶???
            chaan = str.ToCharArray();               //????????????????????¶???


            int m = int.Parse(Console.ReadLine());    //?????£??????????????°
            int[] shuffle = new int[m];

            for (int i = 0; i < m; i++)                    //????????????????????????????????£????????????????´?
            {
                shuffle[i] = int.Parse(Console.ReadLine());
            }

            string answer = new string(Shuffle(chaan, shuffle));

            Answers.Add(answer);
        }


        for (int i = 0; i < Answers.Count; i++)
        {
            Console.WriteLine(Answers[i]);
        }
    }


    static char[] Shuffle(char[] chan,int[] x)
    {
        char[] copy = chan;
        int m = x.GetLength(0);

        for (int i = 0; i < m; i++)
        {
            char[] chacha = new char[copy.GetLength(0)];
            int y = x[i];
            
             for (int j =0;j <(chan.GetLength(0)- y) ;j++)
              {
                  chacha[j] = copy[y+j];
              }
             
            
           for (int j=0 ;j < y;j++)
            {
                chacha[(chan.GetLength(0)-y)+j] = copy[j];
            }
            
            copy = chacha;

        }

        char[] answer = copy;

        return answer;
    }
    
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

string a, b;
int memo[2000][2000];

int solve(int ai=0, int bi=0) {

    if (ai == a.size()+1 and bi == b.size()+1) {
        return 0;
    }

    int& res = memo[ai][bi];
    if (res < 1e8) return res;

    if (a[ai] == b[bi]) res = solve(ai+1, bi+1);
    else {
        if (ai < a.size() and bi < b.size()) {
            res = min(res, solve(ai+1, bi+1)+1);
        }
        if (ai < a.size()) {
            res = min(res, solve(ai+1, bi)+1);
        }
        if (bi < b.size()) {
            res = min(res, solve(ai, bi+1)+1);
        }
    }

    return res;
}

int main() {
    cin >> a >> b;
    fill(memo[0], memo[2000], 1e8);
    cout << solve() << endl;
    return 0;
}



Measured memory_bytes: 18880
#include <bits/stdc++.h>
#define int long long
#define INF 1ll<<60
using namespace std;
int gcd(int a,int b){
	if(a%b==0)
		return b;
	return gcd(b,a%b);
}
signed main(){
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int N,Q;
  cin>>N>>Q;
  N--;
  for(int i=Q-N;i<=Q+N;i++){
  	cout<<i<<' ';
  }
  cout<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
int main() {
	int n, k; std::cin >> n >> k;
	std::vector<int> p(n, 0);
	for (int i = 0; i < n; i++) std::cin >> p[i];
	std::sort(p.begin(), p.end());
	int ans = 0;
	for (int i = 0; i < k; i++) ans += p[i];
	std::cout << ans << std::endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n, m = 0, sum = 0; cin >> n;
  for(int i = 0; i < n; ++i) {
    int x; cin >> x;
    m = max(x, m);
    sum+=x;
  }
  cout << ((sum-m>m ? "Yes" : "No"));
}



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

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

    for (int k = 1; k <=n ; ++k) {
        if(a[k-1] <= a[k] && a[k] <= a[k+1]) cout << sum << endl;
        else {
            cout << sum - (abs(a[k] - a[k-1]) + abs(a[k] - a[k+1])) + abs(a[k-1] - a[k+1]) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define chmax(a, b) a = (a >= b ? a : b)
#define chmin(a, b) a = (a <= b ? a : b)
#define out(a) cout << a << endl
#define outa(a, n) { rep(_, n) cout << a[_] << " "; cout << endl; }
#define outp(a, n) { cout << endl; rep(_, n) cout << a[_].F << " " << a[_].S << endl; }
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
#define FIX(a) fixed << setprecision(a)
#define LB(v, n) (int)(lower_bound(all(v), n) - v.begin())
#define UB(v, n) (int)(upper_bound(all(v), n) - v.begin())
ll pow(ll a, int b) {return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1;}
ll nck(int n, int k) { ll ret = 1; rep(i, k) {ret *= n - i; ret /= i + 1; } return ret; } // n <= 60
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n, k;
    cin >> n >> k;
    int a;
    cin >> a;
    int g = a;
    int mmax = a;
    rep(i, n - 1) {
        cin >> a;
        g = gcd(g, a);
        chmax(mmax, a);
    }
    // out(mmax << " " << k << " " << g);
    if (mmax >= k && k % g == 0) {
        out("POSSIBLE");
        return 0;
    }
    out("IMPOSSIBLE");
    
    // 4 7
    // 7 7 7 7
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
void out(vector<int> &v){
    rep(i,v.size()){
        if(i)cout << " ";
        cout << v[i];
    }
    cout << endl;
}
signed main(){
    int n; cin >> n;
    vector<int>v(n); erep(e,v) cin >> e;
    rep(i,n){
        for(int j = i-1;j>=0;--j){
            if(v[j]>v[j+1])swap(v[j],v[j+1]);
        }
        out(v);
    }
}





Measured memory_bytes: 3108
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#maincode-------------------------------------------------
n = input()
if '7' in n:
    print('Yes')
else:
    print('No')

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

using namespace std;

long long x[4], y[4];

const long long mod = 1e9;

int main()  {
	long long s;
	cin >> s;
	x[1] = 0, y[1] = 0;
	long long rest = s % mod;
	long long aa = mod - rest;
	if(rest == 0)
        aa = 0;
    x[3] = aa, y[2] = 1;
    s += aa;
    x[2] = mod, y[3] = s / x[2];
    for(int i = 1;i <= 3;i++)
        cout << x[i] << " " << y[i] << " ";
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
        checked {
#if DEBUG
            MyDebugger.Test(process, "../TextFile1.txt");
            //TestCaseMaker.MakeTestCase1("../TextFile2.txt");
            //MyDebugger.Test(process, "../TextFile2.txt");
#else
            object ret = process(new StreamReader(Console.OpenStandardInput()));
            Console.WriteLine(ret);
#endif
        }
    }

    static object process(TextReader input) {
        var spl = input.ReadLine().Split(' ');
        var a = int.Parse(spl[0]);
        var b = int.Parse(spl[1]);
        var c = int.Parse(spl[2]);

        int count = 0;

        for(int i=a; i<=b; i++) {
            if(i % c == 0) count++;
        }

        return count;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        if (n == 0) return ret;
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

class UnionFind {
    using i64 = std::int64_t;

private:
    std::vector<i64> par;
    std::vector<i64> sz;

public:
    UnionFind(i64 N) : par(N), sz(N, 1) {
        for (i64 i = 0; i < N; ++i) par[i] = i;
    }
    i64 root(i64 x) {
        return par[x] == x ? x : par[x] = root(par[x]);
    }
    bool same(i64 x, i64 y) {
        return root(x) == root(y);
    }
    void unite(i64 x, i64 y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (sz[x] < sz[y]) std::swap(x, y);
        par[y] = x;
        sz[x] += sz[y];
    }
    i64 size(i64 x) {
        return sz[root(x)];
    }
    void reset(i64 N) {
        par.resize(N);
        for (i64 i = 0; i < N; ++i) par[i] = i;
        sz.assign(N, 1);
    }
};

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif

    ll N, M;
    cin >> N >> M;

    Vl P(N);
    for (ll i = 0; i < N; i++) {
        cin >> P[i];
        --P[i];
    }

    UnionFind uf(N);

    for (ll i = 0; i < M; i++) {
        ll xi, yi;
        cin >> xi >> yi;
        --xi, --yi;
        uf.unite(xi, yi);
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        if (uf.same(i, P[i])) {
            ++ans;
        }
    }

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue

using namespace std;
typedef long long ll;
ll const inf = 1e9;
ll const mod = 1e9 + 7;

int main()
{
    int n, k;
    cin >> n >> k;
    int a[n];
    fr(i, 0, n) cin >> a[i];
    cout << ((n - 1) + (k - 1) - 1) / (k  - 1) << endl;
    return 0;
}



Measured memory_bytes: 640
//*** 1010101010101010101 ***//
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x;
  cin >> x;
  int y = x;
  while (true) {
    bool prime = true;
    if (y == 1) {
      ++y;
      continue;
    }
    for (int j = 2; j * j <= y; j++) {
      if (y % j == 0) {
        prime = false;
        break;
      }
    }
    if (prime) {
      cout << y << '\n';
      return 0;
    }
    ++y;
  }
  return 0;
}


Measured memory_bytes: 256
n, m, r = gets.split.map(&:to_i)
rr = gets.split.map{|e| e.to_i - 1}

d = Array.new(n) {Array.new(n, 1 << 30)}
n.times {|i| d[i][i] = 0}

m.times do
    a, b, c = gets.split.map{|e| e.to_i - 1}
    d[a][b] = d[b][a] = c + 1
end

n.times do |k|
    n.times do |s|
        next if s == k
        n.times do |f|
            d[s][f] = [d[s][f], d[s][k] + d[k][f]].min
        end
    end
end

p rr.permutation.map {|e| e.each_cons(2).inject(0){|r,(i,j)| r + d[i][j]}}.min

Measured memory_bytes: 15324
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
int a[114514],ab[114514],abc[114514];
int modpow(int x,int k){
	// x ^ k mod inf
	int res = 1;
	while(k>=1){
		if(k%2)res = (res*x)%inf;
		x = (x*x)%inf;
		k >>=1;
	}
	return res;
}
signed main(){
	string str;
	cin>>str;
	int ht = 0;
	int n = str.size();
	for(int i=1;i<=n;i++){
		if( str[i-1] == 'A' ){
			a[i] = a[i-1] + modpow(3,ht);
			ab[i] = ab[i-1];
			abc[i] = abc[i-1];
		}
		if( str[i-1] == 'B' ){
			a[i] = a[i-1];
			ab[i] = ab[i-1] + a[i-1];
			abc[i] = abc[i-1];
		}
		if( str[i-1] == 'C'){
			a[i] = a[i-1];
			ab[i] = ab[i-1];
			abc[i] = abc[i-1] + ab[i-1];
		}
		if( str[i-1] == '?'){
			a[i] = 3 * a[i-1] + modpow(3,ht);
			ab[i] = 3 * ab[i-1] + a[i-1];
			abc[i] = 3 * abc[i-1] + ab[i-1];
			ht++;
		}
		a[i] %= inf;
		ab[i] %= inf;
		abc[i] %= inf;
	}
	cout<<abc[n]<<endl;
	return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include <vector>

using namespace std;

struct node {
	long long key;
	int left;
	int right;
};

vector<node> tree;

void preorder_walk(int ind) {
	if (ind < 0) {
		return;
	}
	cout << " " << tree[ind].key;
	preorder_walk(tree[ind].left);
	preorder_walk(tree[ind].right);
	return;
}

void inorder_walk(int ind) {
	if (ind < 0) {
		return;
	}
	inorder_walk(tree[ind].left);
	cout << " " << tree[ind].key;
	inorder_walk(tree[ind].right);
	return;
}

void insert(int ind) {
	if (ind == 0) {
		return;
	}
	bool find = false;
	int now = 0;
	while (!find) {
		if (tree[now].key < tree[ind].key) {
			if (tree[now].right == -1) {
				tree[now].right = ind;
				find = true;
			}
			else {
				now = tree[now].right;
			}
		}
		else {
			if (tree[now].left == -1) {
				tree[now].left = ind;
				find = true;
			}
			else {
				now = tree[now].left;
			}
		}
	}
	return;
}

bool find_key(int num) {
	int now = 0;
	while (now >= 0) {
		if (tree[now].key == num) {
			return true;
		}
		else if (tree[now].key < num) {
			now = tree[now].right;
		}
		else {
			now = tree[now].left;
		}
	}
	return false;
}

int main(void) {
	int nop;
	cin >> nop;

	string ope;
	int ind = 0;
	long long num;
	tree = vector<node>(nop,{-1,-1,-1});
	for (int q = 0; q < nop; ++q) {
		cin >> ope;
		if (ope == "print") {
			inorder_walk(0);
			cout << endl;
			preorder_walk(0);
			cout << endl;
		}
		else {
			if (ope == "insert") {
				cin >> tree[ind].key;
				insert(ind);
				++ind;
			}
			else {
				cin >> num;
				if (find_key(num)) {
					cout << "yes" << endl;
				}
				else {
					cout << "no" << endl;
				}
			}
		}
	}
	return 0;
}



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

#define int long long
#define forn(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) (x).size())


int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a, b;
	cin >> a >> b;
	if (a >= 1 && a <= 9 && b >= 1 && b <= 9) cout << a * b << endl;
	else cout << -1 << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[2000];
int main()
{
	int n,k,sum=0;
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	reverse(a,a+n);
	for(int i=0;i<k;i++)
		sum+=a[i];
	cout<<sum;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define REP(i, n) for(i=0; i<n; i++)
#define REPR(i, n) for(i=n; i>=0; i--)
#define FOR(i, m, n) for(i=m; i<n; i++)
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 1000000000
#define MOD 1000000007LL
#define MAX 100005
#define NIL -1
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> doup;

int main(void) {
    ll N;
    cin >> N;
    ll i, a[100];
    ll alice=0, bob=0;
    for(i=0; i<N; i++) {
        cin >> a[i];
    }
    sort(a, a+N);
    ll r=0;
    for(i=N-1; i>=0; i--) {
        if(r==0) alice+=a[i];
        else bob+=a[i];
        r=1-r;
    }
    
    cout << alice-bob << endl;
}


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

   typedef long long ll;
   typedef pair<ll, ll> P;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   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; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

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

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

int main(){
   string S, T; cin >> S >> T;
   S += S;
   cout << (~S.find(T) ? "Yes" : "No") << endl;
//   S.find(T) ? cout << "Yes\n" : cout << "No\n";
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#define N 10000
int naturalnumber(int x);
int main(void){

  int A[N], i, n, j, c=0, s;

  scanf("%d",&n);

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

  for(i = 0; i < n; i++){
    s = A[i];
    if(naturalnumber(s) == 1) c++;
  }
  printf("%d\n", c);
  return 0;
}

int naturalnumber(s){
  int j;

  if(s == 2 || s == 3 || s == 5 || s == 7) return 1;
  if(s%2 == 0) return 0;
  for(j = 3; j <= sqrt(s); j += 2){
    if(s%j == 0) return 0;
  }

  return 1;
}

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

int solve(){
    vector < string > w={"Sunny", "Cloudy", "Rainy"};
    map < string , string > nxt;
    for(int i=0;i<3;++i){
        nxt[w[i]]=w[(i+1)%3];
    }

    string s;cin>>s;
    cout<<nxt[s]<<endl;
}

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


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <unordered_set>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
static const int INF = 1000010000;
static const int NIL = -1;
static const int MOD = 1000000007;
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb push_back
#define mp make_pair
#define np next_permutation
#define pq priority_queue
 
int gcd(int a, int b) { int c; while (b != 0) { c = a%b; a = b; b = c; }return a; }
int lcm(int a, int b) { int c = gcd(a, b); a /= c; return a*b; }
int nCr(int a, int b) { int i, r = 1; for (i = 1; i <= b; i++) { r *= (a + 1 - i); r /= i; }return r; }
int pow(int a, int b) { int i, r = 1; for (i = 1; i <= b; i++) { r *= a; }return r; }
long long llpow(long long a, long long b) { long long i, r = 1; for (i = 1; i <= b; i++) { r *= a; }return r; }
long long llgcd(long long a, long long b) { long long c; while (b != 0) { c = a%b; a = b; b = c; }return a; }
long long lllcm(long long a, long long b) { long long c = llgcd(a, b); a /= c; return a*b; }
long long llnCr(long long a, long long b) { long long i, r = 1; for (i = 1; i <= b; i++) { r *= (a + 1 - i); r /= i; }return r; }
 
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};

//--- N < 1000 →　エラトステネスで素数列挙　素因数分解　約数定理

bool isprime[1001];

void hurui(){
    REP(i, 1000) isprime[i] = true;
    isprime[1] = false;
    FOR(i, 2, 1000) if(isprime[i]) for(ll j = 2 * i; j <= 1000; j += i) isprime[j] = false;
}

ll soinsu[1001];

void bunkai(ll x){
    while(x != 1){
        FOR(i, 2, 1000){
            if(x % i == 0 && isprime[i]){
                x /= i;
                soinsu[i]++;
                break;
            }
        }
    }
}

int main(){
    hurui();
    ll n;
    cin >> n;
    REP(i, 1001){
        soinsu[i] = 0;
    }
    FOR(i, 1, n + 1){
        bunkai(i);
    }
    ll ans = 1;
    REP(i, 1001){
        ans = (ans * (soinsu[i] + 1)) % MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
int n;
int arr[200001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string x;
    cin>>x;
    if (x=="ABC") cout<<"ARC";
    else cout<<"ABC";
    /*
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>arr[i];
    }
    */
}

Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
  int n, t, s;
  scanf("%d%d%d", &n, &t, &s);
  vector<int> a(n), b(n);
  REP(i, n) scanf("%d%d", &a[i], &b[i]);

  vector<vector<int> > dp(n+10, vector<int>(t+10, 0));
  dp[0][0]=0;
  REP(i, n){
    REP(j, t+1){
      dp[i+1][j]=max(dp[i][j], dp[i+1][j]);
      
      if(j+b[i]<=t){
	if(s<=j || j+b[i]<=s){
	  dp[i+1][j+b[i]]=max(dp[i+1][j+b[i]], dp[i][j]+a[i]);
	}
      }
    }
  }

  int ans=0;
  REP(i, t+1) ans=max(ans, dp[n][i]);
  printf("%d\n", ans);
}

Measured memory_bytes: 36640
INF = 10**9 + 7


def main():
    from bisect import bisect_left
    N = int(input())
    P = [int(input()) for i in range(N)]

    dp = [INF]*(N)
    for i in range(N):
        idx = bisect_left(dp, P[i])
        dp[idx] = P[i]
    print(bisect_left(dp, INF))


if __name__ == '__main__':
    main()



Measured memory_bytes: 10480