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

using namespace std;

int main()
{
  int N, K;
  cin >> N >> K;
  vector<pair<int, int>> v;
  for (int i = 0; i < N; i++)
  {
    int t, d;
    cin >> t >> d;
    v.push_back({d, t});
  }
  sort(v.begin(), v.end(), greater<pair<int, int>>());
  map<int, bool> type;
  priority_queue<int, vector<int>, greater<int>> pq;
  long long base = 0;
  for (int i = 0; i < K; i++)
  {
    if (type[v[i].second])
      pq.push(v[i].first);
    base += v[i].first;
    type[v[i].second] = true;
  }
  long long ans = base + (long long)type.size() * (long long)type.size();
  for (int i = K; i < N && pq.size() != 0; i++)
    if (!type[v[i].second])
    {
      base -= pq.top();
      pq.pop();
      type[v[i].second] = true;
      base += v[i].first;
      ans = max(ans, base + (long long)type.size() * (long long)type.size());
    }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4212
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N;
  long long int sum = 1;
  cin>>N;
  char arr[N];
  for(int i = 0;i < N;i++){
    cin>>arr[i];
  }
  char c = arr[0];
  for(int i = 1;i < N;i++){
    if(arr[i] == c){

    }else{
      sum += 1;
      c = arr[i];
    }
  }
  cout<<sum<<'\n';
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>    
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//using namespace __gnu_pbds; 
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cout<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define int long long 
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
const ll MOD     = 1000*1000*1000+7;
const ll INF     = 1ll*1000*1000*1000*1000*1000*1000 + 7;
const ll MOD2    = 998244353;
const ll N       = 1000 * 100 + 10;
const ll N2      = 70;
const ld PI  = 3.141592653589793;
//template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll power(ll x,ll y,ll p = LLONG_MAX ){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}

signed main()
{
    fastio();
    //cout<<fixed<<setprecision(20);
    //CHECK for LONG LONG and LONG DOUBLE
    //*comment for all except cc/cf    
    #ifndef ONLINE_JUDGE    
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
    #endif//*/
    int n;
    cin>>n;
    map<int,int> m;
    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin>>x;
        m[x]++;
        sum+=x;
    }
    int q;
    cin>>q;
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        sum-=(a*m[a]);
        sum+=(b*m[a]);
        m[b]+=m[a];
        m[a]=0;
        cout<<sum<<endl;
    }
    printclock;
    return 0;
}

Measured memory_bytes: 9724
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(long long)(n);++i)
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,-1,1,1,-1};

const int MAX=510000;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  ll n,a,b;
  cin >> n >> a >> b;
  if(a==0 && b==0)cout<<0 << endl;
  else cout << n/(a+b)*a+min(n%(a+b),a)<< endl;
  return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

/*
  let's try computer shogi
*/


ll get2(ll a){
  ll b = 1;
  while(b<=a){
    b = b*2;
  }
  return b;
}

int main(){
  ll n;
  vector<ll> a;
  map<ll,ll> mp;
  ll out = 0;
  cin >> n;
  a.resize(n);
  for(ll i=0;i<n;++i){
    cin >> a[i];
    mp[a[i]] += 1;
  }
  sort(a.begin(),a.end());
  for(ll i=0;i<n;++i){
    //cerr<<a[i]<<" ";
  }
  //cerr<<endl;
  for(ll i=0;i<n;++i){
    if(mp[a[n-1-i]] == 0){
      continue;
    }
    mp[a[n-1-i]] -= 1;
    ll b = get2(a[n-1-i]) - a[n-1-i];
    //cerr<<b<<endl;
    auto itr = mp.find(b);
    if (itr != mp.end()){
      //cerr<<"found"<<endl;
      if (mp[b] > 0){
	mp[b] -= 1;
	out += 1;
      }
    }else{
      //cerr<<"not found"<<endl;
    }
  }
  cout<<out<<endl;
}

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


using namespace std;


#ifdef zxc

#include "debug.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = int64_t;
using ld = long double;
const ld EPS = 1e-8;
const ll MOD = 998244353;
const ld PI = 3.141592653589793;
const int maxn = 1e7 + 100;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

string maze[1001];
int dist[1001][101];

signed main() {
#ifdef zxc
    mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    freopen("../kolya_input.txt", "r", stdin);
//    freopen("../kolya_output.txt", "w", stdout);
#else
    mt19937 mt(228);
//            freopen("", "r", stdin);
//        freopen("hack.out", "w", stdout);
#endif
    fast_io();
    cout.precision(10);
    cout << fixed;
    auto start = chrono::steady_clock::now();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> maze[i - 1];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == 0 && j == 0) {
                continue;
            }
            dist[i][j] = 1000;
            if (i > 0) {
                dist[i][j] = dist[i - 1][j] + (maze[i][j] != maze[i - 1][j]);
            }
            if (j > 0) {
                dist[i][j] = min(dist[i][j], dist[i][j - 1] + (maze[i][j] != maze[i][j - 1]));
            }
//            debug(i, j, dist[i][j]);
        }

    }
    int ans = dist[n - 1][m - 1];
    int black_seg = (ans + 1) / 2;
    if (maze[0][0] == '#' && maze[n - 1][m - 1] == '#') {
        ++black_seg;
    }
    cout << black_seg;
    auto end = chrono::steady_clock::now();
    debug("time", chrono::duration_cast<chrono::milliseconds>(end - start).count() / 1000.0);
}

Measured memory_bytes: 384
import sys

stdin = sys.stdin

ni = lambda: int(ns())
ns = lambda: stdin.readline().rstrip()
na = lambda: list(map(int, stdin.readline().split()))

# code here
N = ni()
T, A = na()
H = na()

ans = 0
min_a = 1000

for i, h in enumerate(H):
    t = T - (h * 0.006)
    a = abs(A - t)

    if min_a > a:
        min_a = a
        ans = i+1

print(ans)


Measured memory_bytes: 3064
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

int main(void){
  int a,b,c,d,e,f;
  REP(i,3){
    cin>>a>>b>>c>>d>>e>>f;
    int t1 = a*3600+b*60+c;
    int t2 = d*3600+e*60+f;
    int ans = t2 -t1;
    int h,m,s;
    h = ans/3600;
    ans%=3600;
    m = ans/60;
    ans%=60;
    s = ans;
    printf("%d %d %d\n",h,m,s);
  }
  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
int main(void){
    int A,B;
    scanf("%d %d",&A,&B);
    int x=A*B;
    if((1<=A&&A<=9)&&(1<=B&&B<=9)){
        printf("%d\n",x);
    }else if((A<1||9<A)||(B<1||9<B)){
        printf("-1\n");
}
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
typedef long long ll;
using namespace std;
typedef pair<int, int> P;



/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/


vector<int> parse(string s, char c)
{
	int pre = 0;
	vector<int> v;
	
	for (int i=0; i<s.length(); i++)
	{
		if (s[i] == c)
		{
			v.push_back(atoi(s.substr(pre, i - pre).c_str()));
			pre = i + 1;
		}
	}
	v.push_back(atoi(s.substr(pre, s.length() - pre).c_str()));
	
	return v;
}


int main()
{
	int m[100][100], mx, sz;
	string s;
	
	rep(i, 100) rep(j, 100) m[i][j] = -1;
	for (sz=0; getline(cin, s); sz++)
	{
		vector<int> v = parse(s, ',');
		REP(v.size()) m[sz][i] = v[i];
	}
	//mには左詰にひし形の情報が入る
	
	int dp[100][100];
	dp[0][0] = m[0][0];
	
	for (int i=1; i<=sz/2; i++)
	{
		for (int j=0; j<=i; j++)
		{
			if (j == 0)
			{
				dp[i][j] = m[i][j] + dp[i-1][0];
			} else if (j == i) {
				dp[i][j] = m[i][j] + dp[i-1][j-1];
			} else {
				dp[i][j] = m[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
			}
		}
	}
	
	for (int i=sz/2+1; i<sz; i++)
	{
		for (int j=0; j<=sz-i; j++)
		{
			dp[i][j] = m[i][j] + max(dp[i-1][j], dp[i-1][j+1]);
		}
	}
	
	cout << dp[sz-1][0] << endl;
	
	return 0;
}

Measured memory_bytes: 1300
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i < n; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll=long long;

int a,b,c,x,y;

int main(){
  cin >> a >> b >> c >> x >> y;
  int n=a*x+b*y;;
  int ans=n;
  int z= max(x,y);
  bitset<2> pat;
  reps(i,2*z){
    if(x<=0) pat.set(0);
    if(y<=0) pat.set(1);
    int k;
    if(pat==0)
      k=n+2*c-a-b;
    if(pat==1)
      k=n+2*c-b;
    if(pat==2)
      k=n+2*c-a;
    if(pat==3)
      k=n+2*c;
    ans=min(ans,k);
    n=k;
    x--;y--;
  }
  cout << ans;
}

Measured memory_bytes: 256
n = int(input())
a = map(int, input().split())

zero = False
minus = 0
mn = 99999999999999999
sum = 0
for i in a:
    if i == 0:
        zero = True
    if i < 0:
        minus += 1
    sum += abs(i)
    mn = min(mn, abs(i))

if not zero and minus % 2 != 0:
    sum -= mn * 2

print(sum)


Measured memory_bytes: 11200
/*IT'S A VERY LONG ROAD BUT IT WILL BE WORTH IT*/
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back 
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define ld long double
#define int long long int
signed main() 
{ 
    fast;
    int a,b,k;
    cin>>a>>b>>k;
    if(k>=a)
    {
        cout<<0<<" ";
        k-=a;
        cout<<max((int)0,b-k);
    }
    else
    {
        cout<<a-k<<" "<<b;
    }
} 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int num[200001];
int main(void){
    // Your code here!
    int n, k, a;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a;
        num[a]++;
    }
    sort(num, num + 200001, greater<int>());
    int res = 0;
    for (int i = k; i < 200001; i++) res += num[i];
    cout << res << endl;
}


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

using namespace std;

#define sz(v)           ((int)((v).size()))
#define clr(v, d)       memset(v, d, sizeof(v))
#define rep(i, v)       for(int i=0; i<sz(v); ++i)
#define lp(i, n)        for(int i=0; i<(int)(n); ++i)
#define lpi(i, j, n)    for(int i=(j); i<(int)(n); ++i)
#define lpd(i, j, n)    for(int i=(j); i>=(int)(n); --i)
#define INF             1000000000

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

void init(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

const int N = 1e6+5;
bool arr[N];

int main()
{
	init();
	ll a, b;
	int ans = 1;
	cin >> a >> b;
	a = __gcd(a, b);
	if(a % 2 == 0){
		++ans;
		while(a % 2 == 0)
			a /= 2;
	}
	b = sqrt(a);
	b = min(1000000LL, b+1);
	for (ll i = 3; i < b; i += 2) {
		if(!arr[i]){
			if(a % i == 0){
				++ans;
				while(a % i == 0)
					a /= i;
			}
			for (ll j = i * i; j < b; j += 2*i) {
		    	arr[j] = 1;
		    }
		}
	}
	if(a > 1)
		++ans;
	cout << ans;
	return 0;
}

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

int d[11];

bool ok(int i) {
    string s = to_string(i);
    rep(i, s.size()) {
        if (d[s[i]-'0']) return false;
    }
    return true;
}

int main() {
    int N, K;
    cin >> N >> K;
    rep(i, K) { int a; cin >> a; d[a]++; }
    for (int i=N; i<=100000; ++i) {
        if (ok(i)) {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
N = int(input())
s = "a"
ans = []
def dfs(s,n):
  if len(s) == n:
    ans.append(s)
    return
  last = 0
  for i in range(len(s)):
    last = max(last,ord(s[i]))
  limit = chr(last+1)
  for i in range(26):
    temp = chr(97+i)
    if temp <= limit:
      dfs(s+temp,n)
dfs(s,N)
print(*ans,sep="\n")

Measured memory_bytes: 18884
#include <bits/stdc++.h>
using namespace std;
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using ll = long long;
constexpr i64 INF = 1010000000000000017LL;
constexpr i64 MOD = 1000000007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) xmax = x; return true;
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) xmin = x; return true;
    return false;
}
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr); ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH) cout << unitbuf;
    }
} PROCON_INIT;

void solve() {
    ll n, a; cin >> n >> a;
    if (a - n%500 >= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

Measured memory_bytes: 256
using System;
using System.Linq;

class Program {
    static void Main(string[] args) {
        var a = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        if (a[0] <= 0 && a[1] >= 0) Console.WriteLine("Zero");
        else if (a[0] > 0) Console.WriteLine("Positive");
        else if (a[1] < 0) {
            Console.WriteLine((a[0] + a[1] + 1) % 2 == 0 ? "Positive" : "Negative");
        }
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 1002
using namespace std;
int n, k;
int dp[N][N];
int main() {
  memset(dp, 0, sizeof(dp));
  cin>>n>>k;
  for (int i = 1; i <= k; ++i) {
  	dp[1][i] = 1;
  }
  for (int i = 2; i <= n; ++i) {
  	int sum=0;
    for (int j =1; j <= k; ++j) {
    	sum += dp[i-1][j];
    }
    for (int j =1 ; j <= k; ++j) {
    	dp[i][j] = sum - dp[i-1][j];
    }
  }
  int tot=0;
  for (int i =1; i <= k; ++i) {
  	tot += dp[n][i];
  }
  cout<<tot<<endl;
  return 0;
}

Measured memory_bytes: 4224
#include <stdio.h>
#include <string.h>

int main()
{
  char S[101];
  int ret, chg_num, len, i;

  ret = scanf("%s", S);
  len = strlen( S );
  chg_num = 0;
  for ( i=0;i<len/2;i++ ) {
    if ( S[i] != S[len-i-1] )
      chg_num++;
  }
  printf("%d\n", chg_num);
}


Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>

int main(void)
{
  char A[100];
  char B[100];
  int n,i,countA=0,countB=0;

  scanf("%d",&n);
  for (i=0;i<n;i++){
    scanf("%s",A);
    scanf("%s",B);
    if (strncmp(A,B,100)>0){
      countA=countA+3;
    }else if(strncmp(A,B,100)<0){
      countB=countB+3;
    }else{
        countA++;
        countB++;
    }
  }

  printf("%d %d\n",countA,countB);
  return 0;
}


Measured memory_bytes: 2048
#include <iostream>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    
    if (a <= b) {
    	if (a <= c) {
    		if (b <= c) {
    			cout << a << " " << b << " " << c << endl;
			} else {
				cout << a << " " << c << " " << b << endl;
			}
		} else {
			cout << c << " " << a << " " << b << endl;
		}
	} else {
		if (a <= c) {
    			cout << b << " " << a << " " << c << endl;
			} else {
				if (c <= b) {
					cout << c << " " << b << " " <<
					 a << endl;
				} else {
					cout << b << " " << c << " " << a << endl;
				}
		}
	}
    return 0;
}


Measured memory_bytes: 3092
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

int main(){
    int n,k;
    cin>>n>>k;
    map<int,int> mp;
    rep(i,n){
        int x;
        cin>>x;
        mp[x]++;
    }
    
    vector<int> nums;
    for(auto e:mp){
        nums.pb(e.second);
    }
    sort(all(nums));
    
    int t = nums.size()-k;
    int ans = 0;
    for(auto elm:nums){
        if(t>0){
            ans += elm;
            t--;
        }else{
            break;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 10748
N,T = map(int,input().split())
time = [int(i) for i in input().split()]
ans = T  
now = 0 
for i in range(N-1):
  now = time[i] + T
  if now > time[i+1]:
    ans += (time[i+1]-time[i]) 
  else:
    ans += T
print(ans)

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

using namespace std;

#define  SZ(items) (int)items.size()
#define  CLR(a)  memset(a,0,sizeof(a))
#define  SET(a)  memset(a,-1,sizeof(a))

template <class T> inline T bigmod(T p, T e, T m)
{
    T ret = 1;
    for (; e > 0; e >>= 1)
    {
        if (e & 1)
            ret = (ret * p) % m;
        p = (p * p) % m;
    }
    return (T)ret;
}

#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1)
{
    cerr << name << " is " << arg1 << std::endl;
}
template < typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args)
{
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " is " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define debug(...)
#endif



void solve()
{

    long long n;
    cin>>n;

    long long res=(n*(n-1))/2ll;
    cout<<res<<endl;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    cout.tie(nullptr);
    cin.tie(nullptr);

    int t = 1;

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

    return 0;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define each(it,v) for(auto &it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

main()
{
        int n,d; cin>>n>>d;
        cout<<ceil((double)n/(2*d+1))<<endl;
}

Measured memory_bytes: 256
// *3 or /2

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>
#include <iomanip>
#include <string>
#include <numeric>

using namespace std;

int n;

int main() {
    cin >> n;

    int res = 0;
    while (n > 0) {
        if (n % 10 == 2) {
            res++;
        }
        n /= 10;
    }

    cout << res << endl;

    return 0;
}


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

using namespace std;
int main()
{
	int a, b, c, d, e, k, ch;
	cin >> a >> b >> c >> d >> e >> k;
	ch = b - a + c - b + d - c + e - d;
	if (ch > k)cout << ":(" << endl;
	else { cout << "Yay!" << endl; }
	return 0;
}

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


int main() {
  int n, k; string s;
  cin >> n >> k >> s;
  int score = 0;
  rep(i,n-1)
    if(s[i]==s[i+1])score++;
  int ans = min(score+(2*k), n-1);
  cout << ans << endl;
  return 0;
  
}

Measured memory_bytes: 512
pro_number, submit_number = [s for s in input().split()]
AC = [0] * int(pro_number)
WA = [0] * int(pro_number)
for i in range(int(submit_number)):
  section,output = [s for s in input().split()]
  if AC[int(section)-1]==0 and output=="WA":
    WA[int(section)-1]=WA[int(section)-1]+1
  
  elif output=="AC":
    AC[int(section)-1]=1

AC_number=0
WA_number=0
for i in range(int(pro_number)):
  if AC[i]==0:
    WA[i]=0
    
  AC_number=AC_number+AC[i]
  WA_number=WA_number+WA[i]

print(AC_number,WA_number)

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

typedef struct {
    int num;
    int p;
    long long y;
    char id[13];
} city_t;

int compare_num(const void *a, const void *b)
{
    return ((city_t*)a)->num - ((city_t*)b)->num;
}

int compare_p(const void *a, const void *b)
{
    return ((city_t*)a)->p - ((city_t*)b)->p;
}

int compare_y(const void *a, const void *b)
{
    if (((city_t*)a)->y - ((city_t*)b)->y < 0)
        return -1;
    if (((city_t*)a)->y - ((city_t*)b)->y > 0)
        return 1;
    return 0;
}

int main (void)
{
    int N, M;
    city_t city[(int)1e5];
    int i, start = 0, end = 0, x = 1;

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

    for (i = 0; i < M; i++) {
        city[i].num = i;
        scanf("%d %lld", &city[i].p, &city[i].y);
    }

    qsort(city, M, sizeof(city_t), compare_p);

    // for (i = 0; i < M; i++) {
    //     printf("%d %lld %s\n", city[i].p, city[i].y, city[i].id);
    // }

    while (start < M) {
        for (end = start; end < M; end++) {
            // printf("%d==%d?\n", city[end].p, city[end + 1].p);
            if (city[end].p != city[end + 1].p) break;
        }
        // printf("%d->%d\n", start, end);
        qsort(&city[start], end - start + 1, sizeof(city_t), compare_y);
        start = end + 1;
    }

    for (i = 0; i < M; i++) {
        sprintf((char*)&city[i].id, "%06d%06d", city[i].p, x++);
        if (city[i].p != city[i + 1].p) x = 1;
    }

    // for (i = 0; i < M; i++) {
    //     printf("%d %lld %s\n", city[i].p, city[i].y, city[i].id);
    // }

    qsort(city, M, sizeof(city_t), compare_num);

    for (i = 0; i < M; i++) {
        puts(city[i].id);
    }
}


Measured memory_bytes: 7748
#include <bits/stdc++.h>
using namespace std;int A,B,C,X,Y;priority_queue<int,vector<int>,greater<int> >q;int main(){cin>>A>>B>>C>>X>>Y;q.push(A*X+B*Y);q.push(2*C*max(X,Y));if(X>Y)q.push((X-Y)*A+2*C*Y);else q.push((Y-X)*B+2*C*X);cout<<q.top()<<endl;}

Measured memory_bytes: 256
#include <stdio.h>

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

void fillS(int y, int x);
void fillM(int y, int x);
void fillL(int y, int x);
int in(int y, int x) {
  return 0<=y&&y<10&&0<=x&&x<10;
}

int main() {
  int x, y, s;
  while(scanf("%d,%d,%d", &x, &y, &s) != EOF) {
    if(s == 1) fillS(y, x);
    else if(s == 2) fillM(y, x);
    else if(s == 3) fillL(y, x);
  }
  {
    int cnt = 0;
    int mx = 0;
    int i, j;
    for(i = 0; i < 10; i++) {
      for(j = 0; j < 10; j++) {
	//printf("%d", mas[i][j]);
	if(mas[i][j] == 0) cnt++;
	if(mx < mas[i][j]) mx = mas[i][j];
      }
      //puts("");
    }
    printf("%d\n%d\n", cnt, mx);
  }
  return 0;
}

void fillS(int y, int x) {
  int i;
  mas[y][x]++;
  for(i = 0; i < 4; i++) {
    if(in(y+dy[i], x+dx[i])) {
      mas[y+dy[i]][x+dx[i]]++;
    }
  }
}

void fillM(int y, int x) {
  int i;
  mas[y][x]++;
  for(i = 0; i < 8; i++) {
    if(in(y+dy[i], x+dx[i])) {
      mas[y+dy[i]][x+dx[i]]++;
    }
  }
}

void fillL(int y, int x) {
  int i;
  fillM(y, x);
  for(i = 0; i < 4; i++) {
    if(in(y+dy[i]+dy[i], x+dx[i]+dx[i])) {
      mas[y+dy[i]+dy[i]][x+dx[i]+dx[i]]++;
    }
  }
}

Measured memory_bytes: 600
// C - Strange Bank
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n; cin>>n;
	int dp[n+1];
	for(int i=0; i<=n; ++i) dp[i] = i;
	for(int yen=6; yen<=n; ++yen){
		for(int c=6; c<=yen; c*=6)
			dp[yen] = min(dp[yen], dp[yen-c] + 1);
		for(int c=9; c<=yen; c*=9)
			dp[yen] = min(dp[yen], dp[yen-c] + 1);
	}
	cout<< dp[n] <<endl;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

struct Solver {
	void solve() {
		int X, Y;
		cin >> X >> Y;

		int ans = 0;
		if( X <= 3 ) { ans += 100000 * (4-X); }
		if( Y <= 3 ) { ans += 100000 * (4-Y); }
		if( X == 1 && Y == 1 ) { ans += 400000; }

		cout << ans << endl;
	}
};

int main() {
	ios::sync_with_stdio( false );
	cout << fixed << setprecision( 10 );
	Solver().solve();

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool cmp (int a,int b)
{   return a>b;
}
int p[100005],q[100005],r[100005];
int main ()
{   int x,y;
    int A,B,C;
    scanf("%d %d %d %d %d",&x,&y,&A,&B,&C);
    for(int i=0;i<A;i++)
       cin>>p[i];
    for(int i=0;i<B;i++)
       cin>>q[i];
    for(int i=0;i<C;i++)
       cin>>r[i];
      sort(p,p+A,cmp);  sort(q,q+B,cmp);  sort(r,r+C,cmp);
      long long sum=0;
      for(int i=0;i<x;i++)    sum+=p[i];
       //printf("%d\n",sum);
      for(int i=0;i<y;i++)    sum+=q[i];
      //printf("%d\n",sum);
      for(int i=0;i<C;i++)
      {   if(x==0)    {
      	  if(r[i]>q[y-1])   sum=sum-q[x-1]+r[i],y--;
	       continue;}
           if(y==0)  
		   {   if(r[i]>p[x-1])   sum=sum-p[x-1]+r[i],x--;
			     continue;
			 }
	      if(r[i]<p[x-1]&&r[i]<q[y-1])  break;
          else
           {   if(p[x-1]<q[y-1])
                 { if(r[i]>p[x-1])   sum=sum-p[x-1]+r[i],x--;}
                else
                 {   sum=sum-q[y-1]+r[i],y--;
				 }
		   }
	  }
	  printf("%lld",sum);
}

Measured memory_bytes: 1408
from collections import Counter
from operator import itemgetter
N = int(input())
D = list(map(int, input().split()))
MOD = 998244353

class Mint:
    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def __init__(self, val, mod=10**9+7):
        val = Mint.get_value(val)
        self.__mod = mod
        self.__val = val % self.__mod

    @property
    def value(self): return self.__val
    @property
    def inverse(self): return pow(self.__val, self.__mod - 2, self.__mod)

    def __eq__(self, other): return self.__val == other.val
    def __ne__(self, other): return self.__val != other.val

    def __neg__(self): return Mint(self.__val, self.__mod)

    def __iadd__(self, other):
        other = Mint.get_value(other)
        self.__val = (self.__val + other) % self.__mod
        return self
    def __add__(self, other):
        new = Mint(self.__value, self.__mod)
        new += other
        return new
    def __radd__(self, other): return self + other

    def __isub__(self, other):
        other = Mint.get_value(other)
        self.__val = (self.__val - other + self.__mod) % self.__mod
        return self
    def __sub__(self, other):
        new = Mint(self.__value, self.__mod)
        new -= other
        return new
    def __rsub__(self, other):
        new = Mint(Mint.get_value(other), self.__mod)
        new -= self
        return new

    def __imul__(self, other):
        other = Mint.get_value(other)
        self.__val = self.__val * other % self.__mod
        return self
    def __mul__(self, other):
        new = Mint(self.__value, self.__mod)
        new *= other
        return new
    def __rmul__(self, other): return self * other

    def __ifloordiv__(self, other):
        other = Mint(other, self.__mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new = Mint(self.__value, self.__mod)
        new //= other
        return new
    def __rfloordiv__(self, other):
        new = Mint(Mint.get_value(other), self.__mod)
        new //= self
        return new

C = Counter(D)

if D[0] != 0 or C[0] != 1:
    print(0)
    exit()

ans = Mint(1, MOD)
expected = 0
for i,c in sorted(C.items(), key=itemgetter(0)):
    if i == 0: continue
    expected += 1
    if i != expected:
        print(0)
        exit()
    ans *= pow(C[i-1], c, MOD)

print(ans.value)


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

int main(){
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  int cnt=0;
  for (int i = 0; i <= A; i++) {
    for (int j = 0; j <= B; j++) {
      for (int k = 0; k <= C; k++) {
        if((500*i+100*j+50*k)==X) cnt++;
      }
    }
  }
  cout << cnt << endl;
}


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

int main(){
    int H,W,N;
    cin >> H >> W >> N;

    if(H >= W){
        if(N % H == 0) cout << (N/H) << endl;
        else cout << (N/H)+1 << endl;
    } else {
        if(N % W == 0) cout << (N/W) << endl;
        else cout << (N/W)+1 << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
ll int gcd (ll int a,ll int b) { return b ? gcd (b, a % b) : a; }

int main()
{
	int n,k;
	cin>>n>>k;
	std::vector<int> v(n);
	int dp[n];
	for (int i = 0; i < n; ++i)
	{
		cin>>v[i];
	}
	dp[0]=0;dp[1]=abs(v[1]-v[0]);
	for(int i=2;i<n;i++)
	{
		int val = INT_MAX;
		int j=1;
		while(j<=k && i-j>=0)
		{
			val = min(dp[i-j]+abs(v[i]-v[i-j]),val);
			//cout<<"hi "<<val<<"\n";
			j++;
		}
		dp[i]=val;
		//cout<<i<<" "<<dp[i]<<"--"<<dp[i-1]<<"--"<<dp[i-2]<<"\n";
	}
	cout<<dp[n-1]<<"\n";
}


Measured memory_bytes: 3984
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
bool dp[5001];
vector<ll> a(0);
vector<vector<bool> > L(0),R(0);
int main()
{
  ll res=0,N,K;
  cin >> N >> K;
  a =  vector<ll>(N,0);
  REP(i,N){
    cin >> a[i];
  }
  sort(a.begin(),a.end());
  L = vector<vector<bool> >(N+1,vector<bool>(5001,false));
  R = vector<vector<bool> >(N+1,vector<bool>(5001,false));
  L[0][0] = true;
  R[N][0] = true;
  for(int i=0;i<N;i++){
    for(int k=0;k<=5000;k++){
      if(k-a[i] >= 0)
        L[i+1][k] = L[i][k] || L[i][k-a[i]];
      else
        L[i+1][k] = L[i][k];
    }
  }
  
  for(int i=N;i>0;i--){
    for(int k=0;k<=5000;k++){
      if(k-a[i-1] >= 0)
        R[i-1][k] = R[i][k] || R[i][k-a[i-1]];
      else
        R[i-1][k] = R[i][k];
    }
  }
  for(int i=0;i<N;i++){
    if(a[i] >= K){
      res++;
      continue;
    }
    for(int k=0;k<=K;k++){
      if(L[i][k]){
        for(int j=K-k-1;j>=K-k-a[i];j--){
          if(R[i+1][j]){
            res++;
            k = K+1;
            break;
          }
        }
      }

    }
  }
  
  
  cout << (N-res) << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
const int MOD = 1000000007;
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


Measured memory_bytes: 6912
N, M = map(int, input().split())
d = []
for i in range(N):
    a, b = map(int, input().split())
    d.append((a, b))
d = sorted(d)
num = 0
ans = 0
for i in range(N):
    a, b = d[i]
    if num + b < M:
        num += b
        ans += a * b
    else:
        ans += a * (M - num)
        break

print(ans)



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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = (int)(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = (int)(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const long long MOD = 1000000007LL;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

lint digit_sum(lint n){
    lint res = 0;
    while(n > 0LL){
        res += n % 10LL;
        n /= 10LL;
    }
    return res;
}

lint next_snuke(lint n){
    int cnt = 2;
    lint tmp = n;
    while(tmp > 0LL){
        tmp /= 10LL;
        ++cnt;
    }
    lint d = 10, res = n + 1LL;
    reps(i, cnt){
        lint now = d * ((n + d) / d + 1LL) - 1LL;
        if(now * digit_sum(res) < res * digit_sum(now)){
            res = now;
        }
        d *= 10LL;
    }
    return res;
}

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

    int k;
    cin >> k;

    lint ans = 1;
    rep(i, k){
        cout << ans << endl;
        ans = next_snuke(ans);
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	int a[n];
	for ( int i=0;i<n;i++)cin>>a[i];
	int b[n];
	b[0]=0;
	b[1]=abs(a[1]-a[0]);
	for( int i=2;i<n;i++){
		b[i]=INT_MAX;
		for ( int j=i-1;j>=i-k;j--){
			if ( j<0)break;
			b[i]=min(b[i],b[j]+abs(a[i]-a[j]));
		}
	}
	cout<<b[n-1]<<endl;
}

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

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

  int v[100],w[1000];
  for(int i=0;i<N;i++){
    cin >> v[i] >> w[i];
  }

  int DP[N+1][W+1];
  for(int i=0;i<=W;i++){
    DP[0][i]=0;
  }

  for(int i=1;i<=N;i++){
    for(int j=0;j<=W;j++){
      if(j<w[i-1])
        DP[i][j]=DP[i-1][j];
      else{
        if(DP[i-1][j]>DP[i-1][j-w[i-1]]+v[i-1])
          DP[i][j]=DP[i-1][j];
        else
          DP[i][j]=DP[i-1][j-w[i-1]]+v[i-1];
      }
    }
  }

  cout << DP[N][W] << endl;

  return 0;
}



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

#include <boost/range/adaptors.hpp>
#include <boost/range/combine.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    cout << 360 / std::gcd(360, n) << std::endl;
}

Measured memory_bytes: 3632
//   Sourav Verma IPG_2013  ABV_IIITMG Task @ Codeforces & Atcoder

#include<bits/stdc++.h>

#define ll                    long long int
#define loop(i,a,b)           for(int i=(int)a;i<(int)b;++i)
#define rloop(i,a,b)          for(int i=(int)a;i<=(int)b;++i)
#define loopr(i,a,b)          for(int i=(int)a;i>=(int)b;--i)
#define count_1(n)            __builtin_popcountll(n)
#define pb                    push_back
#define mset(a,b,c)           loop(i,0,b) a[i]=c
#define F                     first
#define S                     second
#define mp                    make_pair
#define clr(x)                x.clear()
#define MOD                   1000000007
#define MAX                   1e9
#define MIN                   -1e9
#define itoc(c)               ((char)(((int)'0')+c))
#define vi                    vector<int>
#define vvi                   vector<vi>
#define pll                   pair<ll,ll>
#define pii                   pair<int,int>
#define all(p)                p.begin(),p.end()
#define mid(s,e)              (s+(e-s)/2)
#define mini                  INT_MIN
#define sv()                  int t; scanf("%d",&t); while(t--)
using namespace std;
ll extgcd(ll a,ll b,ll& x,ll& y){if(b==0){x=1;y=0;return a;}else{int g=extgcd(b,a%b,y,x);y-=a/b*x;return g;}}
ll lcm(int x, int y) { return x * 1ll * y / (int)__gcd(x, y); }
ll hcf(ll a, ll b) {if(b>a) return (hcf(b, a)); if(a%b==0) return b; return (hcf(b, a%b));} 
ll modpow(ll a,ll b) {ll res=1;a%=MOD;for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}

vi v;
int n,avg;
ll dp[51][51][2501];
ll solve(int i,int j,int k){
	if(i==n && j>0 && k%j==0 && k/j == avg) return 1;
	else if(i==n) return 0;
	if(dp[i][j][k]!=-1) return dp[i][j][k];
	ll p=solve(i+1,j+1,k+v[i]);
	ll q=solve(i+1, j, k);
	return dp[i][j][k] = p+q;
}
int main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0);
    loop(i,0,51){
		loop(j,0,51){
			loop(k,0,2501){
				dp[i][j][k]=-1;
			}
		}
    }
	cin>>n>>avg;
	v.resize(n);
	loop(i,0,n) scanf("%d",&v[i]);
	ll ans = solve(0,0,0);
	cout<<ans;
    return 0;
}

Measured memory_bytes: 51072
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
using namespace std;
typedef long long int lli;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define INF 1000000000
#define IOS ios_base::sync_with_stdio(0); cin.tie(0) //making cin faster
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR_R(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define REP(i,n)   FOR(i,0,n)
#define REP_R(i,n)   FOR_R(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SIZ(x) ((int)(x).size())


int calcGCM(int,int);

int main(void)
{
  int x,y;

  cin >> x >> y;

  cout << calcGCM(x,y) << "\n";
  
  
  
}

int calcGCM(int x ,int y)
{
  if( y < x )
    {
      return calcGCM(y,x);
      
    }
  if( y % x == 0 )
    {
      return x;
      
    }

  return calcGCM( y%x , x  );
  
  
  
}



Measured memory_bytes: 3104
import math

def combinations_count(n, r):
  if n>=r:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  else:
    return 0

str_n=input()
k=int(input())
cnt=0
dig = len(str_n)

#最上位桁が最大以外の場合　かつ　0でない場合
cnt += (int(str_n[0])-1)*combinations_count(dig-1,k-1)*9**(k-1)
#最上位桁が0の場合
if dig-1>=k:
  cnt += combinations_count(dig-1,k)*9**k

#最上位桁が最大の場合
if k==1:
  cnt+=1
else:
  ##第２非ゼロ桁の探索
  for i in range(dig-1):
    if str_n[i+1] != '0':
      dig2 = i+1
      break
  else:
    print(cnt)
    exit()
  ##第２非ゼロ桁が最大以外の場合　かつ　0でない場合
  cnt += (int(str_n[dig2])-1)*combinations_count(dig-1-dig2,k-2)*9**(k-2)
  ##第２非ゼロ桁が0の場合
  if dig-1-dig2>=k-1:
    cnt += combinations_count(dig-1-dig2,k-1)*9**(k-1)
  ##第２非ゼロ桁が最大の場合
  if k==2:
    cnt+=1
  else:
    ##第３非ゼロ桁の探索
    for i in range(dig-1-dig2):
      if str_n[i+1+dig2] != '0':
        dig3 = i+1+dig2
        break
    else:
      print(cnt)
      exit()
    ##第３非ゼロ桁が0でない場合
    cnt += int(str_n[dig3])
    ##第３非ゼロ桁が0の場合
    cnt += combinations_count(dig-1-dig3,k-2)*9**(k-2)
print(cnt)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
 
int main() {
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);
 
    ll straight = min(K, X / D);
    K -= straight;
    X -= straight * D;
 
    if (K % 2 == 0) {
        cout << X << endl;
    } else {
        cout << D - X << endl;
    }
 
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
 
int main(){
int a;
string b;
int cnt = 0;
cin >> a;
    for(int i=1;i<a+1;i++){
        b = to_string(i);
        if(b.size()%2 == 1) cnt++;
    }
    cout << cnt << endl;
}

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

#include <fstream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  /*
  ifstream in("input.txt");
  cin.rdbuf(in.rdbuf());
  //*/
  int N;
  string S;
  cin >> N >> S;
  set<char> si, sj;
  int ans = 0;
  for(int i = 0; i < S.size(); i++){
    int cnt = 0;
    si.clear();
    sj.clear();
    for(int j = 0; j < S.size(); j++){
      if(j <= i){
        si.insert(S[j]);
      } else{
        sj.insert(S[j]);
      }
    }
    for(auto x: si){
      if(sj.count(x)){
        cnt++;
      }
    }
    ans = max(ans, cnt);
  }
  cout << ans <<endl;
}

Measured memory_bytes: 3584
import java.util.*;

class Plant {
    private int length;
    private int glowthOfNobiro;
    private int glowthOfTidime;

    public Plant(int length, int glowthOfNobiro, int glowthOfTidime) {
        this.length = length;
        this.glowthOfNobiro = glowthOfNobiro;
        this.glowthOfTidime = glowthOfTidime;
    }

    public void growPlant(String message) {
        if (message.equals("nobiro")) {
            this.length += this.glowthOfNobiro;
            if (this.length < 0) {
                this.length = 0;
            }
        } else if (message.equals("tidime")) {
            this.length += this.glowthOfTidime;
            if (this.length < 0) {
                this.length = 0;
            }
        } else if (message.equals("karero")) {
            this.length = 0;
        }
    }

    public int getLength() {
        return this.length;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int X = Integer.parseInt(sc.next());
        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());

        Plant plant = new Plant(X, A, B);

        int N = Integer.parseInt(sc.next());
        for (int i = 0; i < N; i++) {
            String S = sc.next();
            plant.growPlant(S);
        }

        System.out.println(plant.getLength());
    }
}




Measured memory_bytes: 29048
import math

X = int(input())
# X = 33981761


def calculate(x):

    b = 0
    while True:
        tmp1 = x + b ** 5
        a1 = math.pow(tmp1, 0.2)

        if (a1 - math.floor(a1) < 1e-7):
            print(int(a1), int(b))
            break

        tmp2 = x + (-1 * b) ** 5
        if tmp2 >= 0:
            a2 = math.pow(tmp2, 0.2)
            if (a2 - math.floor(a2) < 1e-7):
                print(int(a2), int(-1 * b))
                break

        b = b + 1


calculate(X)


Measured memory_bytes: 9384
D, G  = map(int, input().split())
PC = [list(map(int, input().split())) for _ in range(D)]

def dfs(i, count, score, remain):
    global answer
    if i == D:
        if score < G:
            use = max(remain)
            n = min(-(-(G-score)//((use+1)*100)), PC[use][0])
            score += 100*n*(use+1)
            count += n
        if score >= G:
            answer = min(answer, count)
    else:
        dfs(i+1, count, score, remain)
        dfs(i+1, count+PC[i][0], score+PC[i][0]*100*(i+1) + PC[i][1], remain-{i})

answer = float('inf')
dfs(0, 0, 0, set(range(D)))
print(answer)

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

typedef long long ll;

int main() {
    int N, P;
    string S;
    cin >> N >> P >> S;
    if (P == 2 || P == 5) {
        ll ans = 0;
        rep(i, N) {
            if ((S[i] - '0') % P == 0) ans += i + 1;
        }
        cout << ans << "\n";
        return 0;
    }
    vector<int> a(N, 1), b(N + 1, 0), r(P, 0);
    rep(i, N - 1) a[N - 2 - i] = (a[N - 1 - i] * 10) % P;
    rep(i, N) b[i + 1] = (b[i] + (S[i] - '0') * a[i]) % P;
    rep(i, N + 1) r[b[i]]++;
    ll ans = 0;
    rep(i, P) {
        ans += 1LL * r[i] * (r[i] - 1) / 2;
    }
    cout << ans << "\n";
}

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

using namespace std;

#define INF 1e9

int dp[50001];
int main() {
	int n, m; cin >> n >> m;

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

	fill(&dp[0], &dp[0]+50001, INF);
	dp[0] = 0;
	for (int i = 0; i < n; ++i) {
		if (dp[i] < INF) {
			for (int j = 0; j < m; ++j) {
				if (i + v[j] <= n) {
					dp[i+v[j]] = min(dp[i+v[j]], dp[i] + 1);
				}
			}
		}
	}
	cout << dp[n] << endl;
}

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

#define MAXN 200005

using namespace std;

int n, x;
int d[MAXN << 1], h[MAXN];

int main() {
    scanf("%d%d%d", &n, &d[1], &x);
    for (int i = 2; i <= (n << 1); ++i)
        d[i] = d[i - 1] + x;
    for (int i = 1; i <= (n << 1); ++i)
        d[i] += d[i - 1];
    for (int i = 1; i <= n; ++i)
        h[i] = d[i << 1];
    long double ans = 0, sum = 0;
    for (int i = 2; i <= n; ++i)
        sum += 1.0 / i;
    for (int i = 1; i <= n; ++i) {
        ans += 0.5 * (h[i] - h[i - 1]) + 0.25 * abs(h[i] - h[i - 1]) * sum;
        sum = sum + 1.0 / (i + 1) - 1.0 / (n - i + 1);
    }
    printf("%.10Lf\n", ans);
}

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

int MIN( const void *c1, const void *c2 );

int main(void){
  int N,n,d,i,x[402],y[402];
  
  while(1){
    scanf("%d",&N);
    if(N==0)break;
    
    x[0]=0;
    y[0]=0;
    
    if(N==1)printf("1 1\n");
    else {
      for(i=1;i<N;i++){
	
	scanf("%d %d",&n,&d);
	
	if(d==0){x[i]=x[n]-1; y[i]=y[n];}
	else if(d==2){x[i]=x[n]+1; y[i]=y[n];}
	else if(d==1){y[i]=y[n]-1; x[i]=x[n];}
	else if(d==3){y[i]=y[n]+1; x[i]=x[n];}
      }
      
      qsort(x,N,sizeof(int),MIN);
      qsort(y,N,sizeof(int),MIN);
      
      printf("%d %d\n",x[N-1]-x[0]+1,y[N-1]-y[0]+1);
    }
  }
  return 0;
}

int MIN( const void *c1, const void *c2 )
{
  int tmp1 = *(int *)c1;
  int tmp2 = *(int *)c2;
  
  if( tmp1 < tmp2 )  return -1;
  if( tmp1 == tmp2 ) return  0;
  if( tmp1 > tmp2 )  return  1;
}

Measured memory_bytes: 0
import math

N,D = [int(zz) for zz in input().split()]
X = [[int(zz) for zz in input().split()] for _ in range(N)]

ans = 0
for k in range(N-1):
    for i in range(k+1,N):
        tmp = 0
        for j in range(D):
            tmp += (X[k][j]-X[i][j])**2

        t = math.sqrt(tmp)
        if t == int(t):
            ans += 1

print(ans)


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

using namespace std;

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

    int n, m, c;
    cin >> n >> m >> c;
    int b[m];
    int a[n][m];
    for(int i = 0; i < m; i++)
        cin >> b[i];
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cin >> a[i][j];
    }

    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int res = 0;
        for(int j = 0; j < m; j++)
            res += a[i][j] * b[j];
        if(res + c > 0)
            ans++;
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 256