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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    int A,B,C,X,Y; cin >> A >> B >> C >> X >> Y;
    int ans = 0;
    if(A+B < 2*C){
        ans = A*X+B*Y;
    }
    else{
        int mn = min(X,Y);
        ans += mn*2*C;
        X -= mn;
        Y -= mn;
        if(X){
            if(A < 2*C) ans += X*A;
            else ans += X*2*C;
        }
        else{
            if(B < 2*C) ans += Y*B;
            else ans += Y*2*C;
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main()
{
    #ifdef LOCAL_EXEC
    #else
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #endif // LOCAL_EXEC
    long long int n,x,t,sum=0,i,j;
    string s;
    cin>>s;
    for(i=0;i<s.size();i++){
        sum+=s[i]-'0';
    }
    if(sum%9==0)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VL = vector<long long>;
using VVL = vector<VL>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)
#define REPC(var, start, end) for(int var = start; var <= (int)end; ++var)
#define CLEAR(var, with) memset(var, with, sizeof(var))
#define ALL(x) x.begin(), x.end()
#define LL long long
#define ULL unsigned long long
#define TIME cout << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << endl;

int w, h, n;
struct coord
{
	int x, y, a;
};

vector<coord> coords;
void fill(VVI& area, int x, int y, int a)
{
	if(a == 1) // x < x[i]
	{
		for(int i = 0; i < h; ++i)
			for(int j = 0; j < x; ++j)
				area[i][j] = 1;
	}
	else if(a == 2) // x > x[i]
	{
		for(int i = 0; i < h; ++i)
			for(int j = x; j < w; ++j)
				area[i][j] = 1;
	}
	else if(a == 3) // y < y[i]
	{
		for(int i = 0; i < y; ++i)
			for(int j = 0; j < w; ++j)
				area[i][j] = 1;
	}
	else // y > y[i]
	{
		for(int i = y; i < h; ++i)
			for(int j = 0; j < w; ++j)
				area[i][j] = 1;
	}
	// REP(i,0,h){
	// 	REP(j, 0, w) cerr << area[i][j] << " ";
	// 	cerr << endl;
	// }
}
int white()
{
	VVI area(h, VI(w, 0));
	for(int i = 0; i < sz(coords); ++i)
	{
		int x = coords[i].x, y = coords[i].y, a = coords[i].a;
		fill(area, x, y, a);
	}
	
	int ret = 0;
	for(int i = 0; i < h; ++i)
		ret += count_if(ALL(area[i]), [](int& i){return i == 0;});
	return ret;		
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
//	freopen("tmp.in", "r", stdin);
	//freopen("tmp.out", "w", stderr);
#endif
	cin >> w >> h >> n;

	coords.resize(n);
	int x, y, a;
	REP(i, 0, n) {
		cin >> x >> y >> a;
		coords[i].x = x; coords[i].y = y; coords[i].a = a;
	}

	cout << white() << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
using namespace std;
//using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long 
#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,arr,n) for(int i=arr;i<=n;i++)
#define repd(i,arr,n) for(int i=arr;i>=n;i--)
#define trav(arr,x) for(auto& arr:x)
#define all(c) c.begin(), c.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(arr) arr.size()
#define pi 3.14159265358979323846
#define MAX 500003
#define vi vector<int>
#define pii pair<int,int>
#define pqueue priority_queue<int>
#define pdqueue priority_queue<int,vi,greater<int> >
//#define endl "\n"
 
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const int mod=998244353;
int power(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a);
        }
        a=(a*a);
        b>>=1;
    }
    return ans;
}

int32_t main()
{
    fast;
    
    int t;
    t=1;
    while(t--)
    {
        char ch;
        cin>>ch;

        if(ch<='Z' && ch>='A') cout<<'A'<<endl;
        else cout<<'a';
    }
}


Measured memory_bytes: 3636
n, m , c = map(int, input().split())
b = list(map(int, input().split()))
ans = 0
for i in range(n):
    a = list(map(int, input().split()))
    cnt = 0
    for j in range(m):
        cnt += a[j]*b[j]
        
    if cnt + c > 0:
        ans +=1
        
print(ans)

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)

int main() {
    int a,b; cin >> a >> b;
    if((a+b)%2 == 1) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    int k = (a + b)/2;
    if(abs(a-k), abs(b-k)) cout << k << endl;
    else cout << "IMPOSSIBLE" << endl;

    return 0;

    
}


Measured memory_bytes: 256
m, d = map(int, input().split())
ans = 0
for i in range(4, m+1):
    for j in range(22, d+1):
        d1 = j%10
        d2 = (j-d1)/10
        if d1>=2 and d2 >=2 and d1*d2 == i:
            ans+=1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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 (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

int main(){
    int n,h;
    cin>>n>>h;
    vector<int> a(n),b(n);
    rep(i,n) cin>>a[i]>>b[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans=0;
    rep(i,n){
        int j=n-1-i;
        if(h<=0)break;
        if(b[j]<a[n-1])break;
        h-=b[j];
        ++ans;
    }

  
    if(h>0){
        ans+=(h+a[n-1]-1)/a[n-1];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std; 
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair <int,int> PII;
typedef pair <ll, ll> PLL;
typedef pair <int,string> PIS;
typedef vector <int> vec;
typedef priority_queue<int> PQ;
#define endl '\n'
#define pi 3.141592653589793
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define fori(z,n) for(int i=z;i<n;i++)
#define forii(z,n) for(int i=z;i<=n;i++)
int maxElement(int arr[],int n)
{
    int maxi=arr[0];
    for(int i=1;i<n;i++)
    {
        if(arr[i]>maxi)
            maxi=arr[i];
    }
    return maxi;
}
int minElement(int arr[],int n)
{
    int mini=arr[0];
    for(int i=1;i<n;i++)
    {
        if(arr[i]<mini)
            mini=arr[i];
    }
    return mini;
}
string trim(const string& str)
{
    int first = str.find_first_not_of(' ');
    if (string::npos == first)
    {
        return str;
    }
    int last = str.find_last_not_of(' ');
    return str.substr(first, (last - first + 1));
}
int main() 
{ 
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;cin>>n>>k;
    ll h[n+1];
    fori(1,n+1)cin>>h[i];
    ll dp[n+1];
    dp[1]=0;
    fori(2,n+1)
    {
        dp[i]=LLONG_MAX;
        for(int p=i-1;p>=max(i-k,1);p--)
            dp[i]=min(dp[i],dp[p]+abs(h[p]-h[i]));
    }
    /* fori(1,n+1) */
    /*     cout<<dp[i]<<" "; */
    /* cout<<endl; */
    cout<<dp[n]<<endl;
    cerr<<"Time elapsed"<<1.0*clock()/CLOCKS_PER_SEC<<"s\n";
    return 0;
}


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

using namespace std;

#define int long long
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int,int> PI;
typedef pair<int,pair<int,int>> PII;
static const int INF=1010000000000000017LL;
static const double eps=1e-12;
static const double pi=3.14159265358979323846;
static const int dx[4]={1,-1,0,0};
static const int dy[4]={0,0,1,-1};
static const int ddx[8]={1,-1,0,0,1,1,-1,-1};
static const int ddy[8]={0,0,1,-1,1,-1,1,-1};

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

string S;

signed main(){
    cin>>S;
    bool yymm=false,mmyy=false;
    if((S[0]-'0'==1&&S[1]-'0'<=2)||(S[0]-'0'==0&&S[1]-'0'<=9&&S[1]-'0'>0))mmyy=true;
    if((S[2]-'0'==1&&S[3]-'0'<=2)||(S[2]-'0'==0&&S[3]-'0'<=9&&S[3]-'0'>0))yymm=true;
    if(yymm&&mmyy)cout<<"AMBIGUOUS"<<endl;
    else if(yymm)cout<<"YYMM"<<endl;
    else if(mmyy)cout<<"MMYY"<<endl;
    else cout<<"NA"<<endl;
}

Measured memory_bytes: 3608
import java.util.*;

public class Main {
    static Scanner scanner;
    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        
        int[] arr = new int[scanner.nextInt()];
        
        for(int i = 0; i < arr.length; ++i) {
            arr[i] = scanner.nextInt();
        }
        
        for(int i = arr.length - 1; i >= 0; --i) {
            System.out.print(arr[i] + (i != 0 ? " " : ""));
        }
        System.out.println();
    }
}


Measured memory_bytes: 26512
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

struct T{int a, b, c;};

int main() {
    int n, q;
    cin >> n >> q;
    vector<T> times;
    for (int i = 0; i < n; i++) {
        int s, t, x;
        cin >> s >> t >> x;
        times.push_back({s - x, 1, x});
        times.push_back({t - x, 2, x});
    }
    for (int i = 0; i < q; i++) {
        int d; cin >> d;
        times.push_back({d, 0, 0});
    }
    sort(times.begin(), times.end(), [](T l, T r) { return l.a < r.a || (l.a == r.a && l.b > r.b); });
    set<int> s;
    for (auto t:times) {
        if (t.b == 1)
            s.insert(t.c);
        else if (t.b == 2)
            s.erase(t.c);
        else
            cout << (s.empty() ? -1 : *(s.begin())) << '\n';
    }
    return 0;
}


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

public class Main {
	static int sum;
	static int[] a,b;
	static int[][] dp;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		for(int test =sc.nextInt();test--!=0;){
			a=new int[9];
			b=new int[9];
			sum=0;
			for(int i=1;i<=18;i++){
				sum+=i;
			}
			dp=new int[sum][(1<<10)-1];
			for(int i=0;i<dp.length;i++){
				Arrays.fill(dp[i], -1);	
				
			}
			for(int i=0;i<9;i++){
				a[i]=sc.nextInt();
			}
			for(int i=0;i<9;i++){
				b[i]=sc.nextInt();
			}
			int q=1;
			for(int i=1;i<=9;i++){
				q*=i;
			}
			System.out.printf("%.5f %.5f\n",(double)dp(0,0)/(double)q,1.0-(double)dp(0,0)/(double)q);
			
		}
	}
	static int dp(int score,int used1){
		if(score>sum/2){
			int bc=9-Integer.bitCount(used1);
			int res=1;
			for(int i = 1;i<=bc;i++){
				res*=i;
			}
			return dp[score][used1]=res;
		}
		if(Integer.bitCount(used1)==9){
			return 0;
		}
//		System.out.println(Integer.toBinaryString(used1)+" "+Integer.toBinaryString(used2));
		if(dp[score][used1]!=-1)return dp[score][used1];
		int res=0;
		for(int i=0;i<9;i++){
			if(((1<<i)&used1)>0)continue;
			int j = Integer.bitCount(used1);
			if(a[i]>b[j]){
				res+=dp(score+a[i]+b[j],used1+(1<<i));
			}
			else{
				res+=dp(score,used1+(1<<i));
			}

		}
		
		
		
		return dp[score][used1]=res;
	}
}

Measured memory_bytes: 45912
import math
N,K=map(int,input().split())
import heapq
A=list(map(int,input().split()))

def isok(x):
  c=0
  for i in range(N):
    c+=math.ceil(A[i]/x)-1
  if c<=K:
    return True
  else:
    return False
start=0
end=max(A)
mid=(start+end)//2
while end-start>1:
  mid=(start+end)//2
  if isok(mid)==True:
    end=mid
  else:
    start=mid
print(end) 

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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define ALL(a) a.begin(),a.end()
#define INIT(a,b) memset(a,b,sizeof(a))
using lint = long long int;

int main() {
    int K;
    string S;
    cin >> K;
    cin >> S;

    int N = S.size();
    if (N <= K) cout << S << endl;
    else cout << S.substr(0,K) << "..." << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <cmath>

using namespace std;
#define rep(i,q) for(int i = 0; (q) > i; i++)

int main(){
  	string s;cin>>s;
  	int bb= 0;
	int bw = 0;
	for(int i = 0; s.size() > i; i++){
    	if(i % 2 == 0){
      		if(s[i] == '0')bb++;
      		else bw++;
    	}
		else{
      		if(s[i] == '0')bw++;
     		 else bb++;
		}
  	}
  	cout << min(bb,bw) << endl;
}


Measured memory_bytes: 512
#include<cstdio>
#include<vector>
using namespace std;

bool isprime[50010];
int ans[50010];

int main()
{
    for(int i=2; i<=50000; i++){
        isprime[i] = true;
    }
    for(int i=2; i<300; i++){
        if(isprime[i]){
            for(int j=i*i; j<=50000; j+=i){
                isprime[j]=false;
            }
        }
    }
    
    vector<int> primes;
    for(int i=2; i<=50000; i++){
        if(isprime[i])primes.push_back(i);
    }
    for(int i=0; primes[i]<=25000; i++){
        for(int j=i; primes[i]+primes[j]<=50000; j++){
            ans[primes[i]+primes[j]]++;
        }
    }
    
    int n;
    while(scanf("%d",&n),n){
        printf("%d\n",ans[n]);
    }
    return 0;
}

Measured memory_bytes: 1352
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>

using namespace std;

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

const long double pi = 3.141592653589793;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define F first
#define S second

// #define COMMENT

/*

const int NN = 200090;
ll fact[NN];
ll finv[NN];
ll inv[NN];

void inverse_modulao() {
  fact[0] = fact[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;

  for(int i = 2;i < NN;i++) {
    fact[i] = fact[i-1]*i%mod;
    inv[i] = mod-mod/i*inv[mod%i]%mod;
    finv[i] = finv[i-1]*inv[i]%mod;
  }
}

ll nCr(int n, int r) {
  return fact[n]*finv[r]%mod*finv[n-r]%mod;
}

*/

ll N, dp[2022][2022];
vector<pair<ll,int>> A(1<<20);

int main() {

//  freopen("input.in","r",stdin);
//  freopen("output.out","w",stdout);

  cin >> N;
  rep(i, N) {
    cin >> A[i].F;
    A[i].S = i;
  }
  // debug(N);
  sort(A.begin(),A.begin()+N);
  rep(i,N) {
    for(int j = 0;j < N-i;j++) {
      if(i==0) {
        dp[i][j]=abs(j-A[i].S)*A[i].F;continue;
      }

      ll u = abs(j-A[i].S)*A[i].F + dp[i-1][j+1];
      ll v = abs(i+j-A[i].S)*A[i].F + dp[i-1][j];
      dp[i][j] = max(u, v);
    }
  }

  cout << dp[N-1][0] << endl;

  return 0;
}


Measured memory_bytes: 42284
"use strict";

var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );

function comp( a, b) {
	return a-b;
}
readable.on( 'data', function( chunk ) {
		var data = chunk.replace( /\n/, '' ).split( ' ' );
		data.sort(comp);
		console.log( data.join( " " ) );
});


Measured memory_bytes: 15516
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void log(A...)(A arg) {
    stderr.writeln(arg);
}
int size(T)(in T s) {
    return cast(int)s.length;
}

class Edge {
    int from, to;
    bool isBridge;
    this(int from, int to) {
        this.from = from;
        this.to = to;
    }
    override string toString() {
        return [from, to, isBridge].to!string;
    }
}
class Graph {
    Edge[][] G;
    int V;
    this(int V) {
        this.V = V;
        G = new Edge[][V];
    }
    void addEdge(int from, int to) {
        G[from] ~= new Edge(from, to);
        G[to] ~= new Edge(to, from);
    }
}

const int INF = int.max/4;
void solve() {
    int N, M; scanf("%d %d\n", &N, &M);
    auto W = stdin.readln.chomp.split(" ").map!(to!int).array;
    auto graph = new Graph(N);
    foreach (i; 0 .. M) {
        int u, v; scanf("%d %d\n", &u, &v); u--; v--;
        graph.addEdge(u, v);
    }
    auto g = graph.G;

    auto visited = new bool[N];
    Tuple!(bool, int, int) dfs(int v, int prev) {
        visited[v] = true;
        int ans = W[v];
        int diff_max = 0;
        bool can_ret = false;
        foreach (e; g[v]) {
            if (e.to == prev) continue;
            if (visited[e.to]) {
                can_ret = true;
                continue;
            }
            auto r = dfs(e.to, v);
            if (r[0]) can_ret = true;
            ans += max(0, r[1]);
            diff_max = max(diff_max, r[2] - max(0, r[1]));
        }
        return tuple( can_ret, (can_ret ? ans : -INF), ans + diff_max);
    }
    dfs(0, -1)[2].writeln;
}


void main() {
    solve();
}

Measured memory_bytes: 32260
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
long double pi=3.14159265358979323846L;
double eps=1e-12;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll popcount(ll n){
    ll ret=0;
    while(n>0){
        ret+=n%2;
        n/=2;
    }
    return ret;
}
ll gya[1000010];
ll kai[1000010];
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
ll bit[800010];
ll u;
void bitinit(ll n){
    ll y=1;
    rep(i,0,69){
        
        if(y>=n){
            u=y;
            break;
        }
        y*=2;
    }
    fill(bit,bit+u+10,0);
}
void add(ll n,ll x){
    ll i=n;
    bit[i]+=x;
    bit[i]%=mod;
    while(i<u){
        i+=i&(-i);
        bit[i]+=x;
        bit[i]%=mod;
    }
}
ll sum(ll n){
    ll i=n;
    ll ret=0;
    while(i>0){
        ret+=bit[i];
        i-=i&(-i);
        ret%=mod;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll h,w;cin>>h>>w;
    if(h%3==0||w%3==0){
        cout<<0<<endl;
        return 0;
    }
    ll ans=inf;
    rep(i,1,h){
        vector<ll> v;
        v.push_back(w/2*(h-i));
        v.push_back((w+1)/2*(h-i));
        v.push_back(i*w);
        sort(v.begin(),v.end());
        ans=min(ans,v[2]-v[0]);
    }
    swap(h,w);
    rep(i,1,h){
        vector<ll> v;
        v.push_back(w/2*(h-i));
        v.push_back((w+1)/2*(h-i));
        v.push_back(i*w);
        sort(v.begin(),v.end());
        ans=min(ans,v[2]-v[0]);
    }
    ans=min(ans,min(h,w));
    cout<<ans<<endl;
}




Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define N 1000000
using namespace std;

int main(){
	int n,k;
	scanf(" %d %d", &n , &k);
	int a[N];
	for(int i=0;i<n;i++){
		scanf(" %d", &a[i]);
	}
	
	int low=0,high=1e9,mid;
	while(1){
		if(high-low <= 1) break;
		mid = (low+high)/2;
		int count=0, bef=0;
		bool f = true;
		while(1){
			if(bef == n) break;
			if(count >= k){
				f = false;
				break;
			}
			int bag = mid;
			int p;
			for(p=bef;p<n;p++){
				if(bag >= a[p]) bag-=a[p];
				else break;
			}
			bef = p;
			count++;
		}
		if(f) high = mid;
		else low = mid;
	}
	
	printf("%d\n", high);	
	return 0;
}

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

using namespace std;

int main() {
	vector<vector<int>> A(3, vector<int>(3));
	for (int i = 0;i<3;++i) {
		for (int j = 0;j<3;++j) {
			cin >> A[i][j];
		}
	}
	int N;
	cin >> N;
	vector<int>B(N);
	for (int n = 0;n<N;++n) {
		cin >> B[n]; 
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (B[n]==A[i][j]) {
					A[i][j] = -1;
				}
			}
		}
	}
	bool b = false;	
	for (int n = 0; n < 3; ++n) {
		if (-3 == A[n][0] + A[n][1] + A[n][2]) {
			b = true;
		}
	}
	for (int n = 0; n < 3; ++n) {
		if (-3 == A[0][n] + A[1][n] + A[2][n]) {
			b = true;
		}
	}
	if (-3==A[0][0]+A[1][1]+A[2][2]) {
		b = true;
	}
	if (-3 == A[0][2] + A[1][1] + A[2][0]) {
		b = true;
	}
	if (b) {
		cout <<"Yes"<<endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3488
H, W = gets.chomp.split(" ").map(&:to_i)
S = H.times.map{gets.chomp}

def BFS(queue) # 幅優先探索
    until queue.empty?
        x, y, depth = queue.shift # x, y　迷路の中の座標　depth 歩数
                                  #　next   スキップ
        next unless 0 <= x && x < W && 0 <= y && y < H # 迷路の外側には出られない
        next if S[y][x] == '#' # 壁の時はスキップ
        next if@flag[y][x] != -1 # 歩数のカウンタ@flag 一度通ったところはいけない
        @flag[y][x] = depth 
        queue << [x + 1, y, depth + 1] #今いるマスの4方のマスに歩数を追加する
        queue << [x - 1, y, depth + 1]
        queue << [x, y + 1, depth + 1]
        queue << [x, y - 1, depth + 1]
    end
end

max = 0
H.times do |h|
    W.times do |w|
        @flag = Array.new(H){Array.new(W, -1)}
        BFS([[w, h, 0]])
        tmp = @flag.map{ |flag| flag.max}.max
        max = tmp if max < tmp
    end 
end

puts max

        

Measured memory_bytes: 2428
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define MOD_Q 998244353
#define PI 3.14159265358979
#define ll long long
using namespace std;

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

	printf("%c", c + 1);
	
	return 0;
}



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

int main() {
    vector<int> a(3);
    for(int i=0;i<3;i++){
        cin>>a.at(i);
    }
    sort(a.begin(),a.end());
    cout << (a.at(1)-a.at(0))+(a.at(2)-a.at(1)) << endl;
}

Measured memory_bytes: 256
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	return tuple( n );
}

auto solve( long n )
{
	return 180 * ( n - 2 );
}


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

const int N_MAX = 200005;
int counter[N_MAX];
int plusc[N_MAX];
vector<int> root[N_MAX];

void dfs(int n, int p, int num){
    int nownum = num + plusc[n];
    counter[n] = nownum;
    for(auto u: root[n]){
        if (u == p)continue;
        dfs(u, n, nownum);
    }
}

int main(){
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        root[a].push_back(b);
        root[b].push_back(a);
    }
    memset(plusc, 0, sizeof(plusc));
    for(int i = 0; i < q; i++){
        int p, x;
        cin >> p >> x;
        plusc[p] += x;
    }

    dfs(1, -1, 0);
    for(int i = 1; i <= n; i++){
        cout << counter[i];
        if (i != n)cout << " ";
    }
    return 0;
}

Measured memory_bytes: 25012
sx, sy, tx, ty = map(int,input().split())

ans = "U"*(ty-sy)
ans += "R"*(tx-sx)
ans += "D"*(ty-sy)
ans += "L"*(tx-sx)

ans += "L"
ans += "U"*(ty+1-sy)
ans += "R"*(tx+1-sx)
ans += "DR"
ans += "D"*(ty-sy+1)
ans += "L"*(tx-sx+1)
ans += "U"

print(ans)

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

#define int int_fast64_t

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

  int x, y; cin >> x >> y;
  y /= x;
  int k=1;
  while (y > 1) {
    y /= 2;
    ++k;
  }
  cout << k << '\n';
}

/*
 * Local variables:
 * compile-command:"g++ -D_GLIBCXX_DEBUG -g3 -ggdb3 -O0 -Wall -Wextra -std=c++14 c.cc -o c && for f in *.in; do echo \"--- $f -------------\"; ./c <$f; done"
 * end:
 */



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

int main()
{
    int N;
    long long sum = 0;
    cin >> N;
    vector<int> Nums(100010, 0);
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        Nums[a]++;
        sum += a;
    }
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++)
    {
        int B, C;
        cin >> B >> C;
        sum += (C - B) * Nums[B];
        Nums[C] += Nums[B];
        Nums[B] = 0;
        cout << sum << endl;
    }
}

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

int main() {
  int a,b,c,d,e;
  cin >> a >> b >> c >> d >> e;
  int m=10;
  int ans=0;
  if(a%10==0){ans+=a;}
  else{ans+=a/10*10+10; m=min(m,a%10);}
  if(b%10==0){ans+=b;}
  else{ans+=b/10*10+10; m=min(m,b%10);}
  if(c%10==0){ans+=c;}
  else{ans+=c/10*10+10; m=min(m,c%10);}
  if(d%10==0){ans+=d;}
  else{ans+=d/10*10+10; m=min(m,d%10);}
  if(e%10==0){ans+=e;}
  else{ans+=e/10*10+10; m=min(m,e%10);}
  ans=ans-10+m;
  cout << ans << endl;
}

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

int main() {

 int S;
  cin >> S;
  
  int h, m, s;
  
  h = S / 3600;
  m = (S % 3600) / 60;
  s = (S % 3600 % 60);
  
  cout << h << ':' << m << ':' << s << endl;
  
  
  return 0;
}


Measured memory_bytes: 3088
using System;
using static System.Console;
using System.Linq;

namespace AC
{
   public class shiokara
   {
      static void Main(string[] args)
      {
          var n = int.Parse(ReadLine());
          var s = ReadLine();
          int ans = 1;
          char[] ss = s.ToCharArray();
          char tmp = s[0];
          for(int i = 1; i < n; i++){
              if(tmp != ss[i]){
                  ans += 1;
                  tmp = ss[i];
              }
          }
          WriteLine(ans);
      }
   }
}

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

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

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

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

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

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

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

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

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

int main()
{
    cout << fixed << setprecision(15);
    vector<ll> A(3);

    cin >> A[0] >> A[1] >> A[2];

    sort(A.begin(), A.end());

    cout << A[2]-A[0] << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    a, b, c = li_input()
    print(a * b // 2)


main()


Measured memory_bytes: 5412
n, m = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(m)]

ans = 1000
if n == 1:
    mn = 0
else:
    mn = 10 ** (n - 1)
for num in range(mn, 10 ** n):
    st = str(num)
    bl = True
    for s, c in sc:
        s -= 1
        if st[s] != str(c):
            bl = False

    if bl:
        ans = min(ans, num)

if ans == 1000:
    ans = -1

print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
using namespace std;
int main(){
	int n, m;
	cin>>n>>m;
	vector<bool>vis(n + 1, false);
	bool ans = false;
	for (int i = 0; i < m; i ++){
		int a, b;
		cin>>a>>b;
		if (a == 1){
			if(vis[b]){
				ans = true;
			}
			vis[b] = true;
		}else if(b == n){
			if (vis[a]){
				ans = true;
			}
			vis[a] = true;
		}
	}
	
	if(!ans)cout << "IM";
	cout << "POSSIBLE" << endl;
	return 0;
}

Measured memory_bytes: 256
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l
    

def main():
    n, q = map(int, input().split())
    bit = BIT(n)
    a = list(map(int, input().split()))
    for i, v in enumerate(a):
        bit.add(i+1, v)

    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            p, x = query[1:]
            bit.add(p+1, x)
        else:
            l, r = query[1:]
            res = bit.get_sum(l, r)
            print(res)


if __name__ == "__main__":
    main()

Measured memory_bytes: 136636
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
#define int long long
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int N;
int a[100100];

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    rep(i, N) cin >> a[i];
    int ans1 = 0;
    int now = 0;
    rep(i, N) {
        if (i%2==0) {
            if (now+a[i]>0) now += a[i];
            else {
                ans1 += 1-(now+a[i]);
                now = 1;
            }
        }
        else {
            if (now+a[i]<0) now += a[i];
            else {
                ans1 += now+a[i]-(-1);
                now = -1;
            }
        }
    }
    int ans2 = 0;
    now = 0;
    rep(i, N) {
        if (i%2==1) {
            if (now+a[i]>0) now += a[i];
            else {
                ans2 += 1-(now+a[i]);
                now = 1;
            }
        }
        else {
            if (now+a[i]<0) now += a[i];
            else {
                ans2 += now+a[i]-(-1);
                now = -1;
            }
        }
    }
    cout << min(ans1, ans2) << endl;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;
#define all(x) x.begin(),x.end()
const ll INF = 1e9;
const ll mod = 1e9 + 7;

int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}

ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    return ((a * b == 0)) ? 0 : (a / gcd(a,b) * b);
}

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


/////////////////////////////////////////////////////////////////////////////////////////

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

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


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

string S;
char U[11]="0123456789";
int junjo[4]={0,0,1,1};

long long STOI(string V){
	int LEN=V.size();
	if(LEN==0){return 0;}
	return (V[LEN - 1] - '0') + 10 * ( STOI(V.substr(0, LEN - 1)) );
}
long long calc(int L,int R){
	int K=0;
	vector<int>junjo2[4];
	for(int i=0;i<4;i++){
		junjo2[junjo[i]].push_back(i);
	}
	for(int i=0;i<4;i++){
		if(junjo2[i].size()>=1){
			for(int j=R-1;j>=L;j--){
				if(S[j]=='('){K++;}
				if(S[j]==')'){K--;}
				for(int k=0;k<junjo2[i].size();k++){
					if(junjo2[i][k]==0){
						if(S[j]=='+' && K==0){
							return calc(L,j)+calc(j+1,R);
						}
					}
					if(junjo2[i][k]==1){
						if(S[j]=='-' && K==0){
							return calc(L,j)-calc(j+1,R);
						}
					}
					if(junjo2[i][k]==2){
						if(S[j]=='*' && K==0){
							return calc(L,j)*calc(j+1,R);
						}
					}
					if(junjo2[i][k]==3){
						if(S[j]=='/' && K==0){
							return calc(L,j)/calc(j+1,R);
						}
					}
				}
			}
		}
	}
	if(S[L]=='(' && S[R-1]==')'){return calc(L+1,R-1);}
	return STOI(S.substr(L,R-L));
}

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>S;
		cout<<calc(0,S.size()-1)<<endl;
	}
}

Measured memory_bytes: 1232
#include <iostream>
#include <queue>
#include <assert.h>   
#include <vector>
#include <algorithm>
#include <time.h>
#include <numeric>
#include <string>
#include <cstring>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <numeric>
#include <deque>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <cstdio>
using namespace std;


//#define double long double
#define int long long
//#define int unsigned long long

#define ll long long
#define ld long double 
#define pi pair<int, int> 
#define pl pair<ll,ll>  
#define pd pair<ld,ld> 
#define str string  
#define mp make_pair
#define vi vector<int> 
#define vl vector<ll> 
#define vd vector<ld> 
#define vs vector<str> 
#define vpi vector<pi> 
#define vpl vector<pl> 
#define vpd vector<pd> 
#define si set<int> 
#define FF(i,j,n) for(signed i=j;i<=n;i++)  
#define DD(i,j,n) for(signed i=j;i>=n;i--) 
#define F(i,j,n) for(signed i=j;i<n;i++)   
#define D(i,j,n) for(signed i=j;i>n;i--) 
#define mem(a,b) memset(a,b,sizeof(a))
#define ndl cout << endl
#define ull unsigned long long 

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;


#define sz(x) (signed)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back() 
#define X first
#define Y second
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


const int mod = 1e9 + 7;

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 


//DEBUG, compile with -DLOCAL
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
  cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
  DBG(t...); }
#ifdef LOCAL 
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define HERE cout << "===GOTHERE===" << endl
#else
#define dbg(...) 42
#define HERE 42
#endif


 /* ============== END OF HEADER ============== */






const int maxn = 1e5*3+20;

int n,_,q,k;

void solve(){
  cin >> n;
  cout << n*(n-1)/2;
}

signed main(){
  //clock_t t1 = clock();  
  IOS
  solve();
  
  //cout << "THE ALGORITHM TOOK: " << (clock() - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << "ms"<< endl;
  return 0;
}

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


//#define FOR(i,0,n) for(int i=0;i<n;i++)
int main() {
  ios_base::sync_with_stdio(false); 
    cin.tie(NULL);cout.tie(NULL);
  // your code goes here
 /* int t;
  cin>>t;
  while (t--)
  {
    */
 
    ll i,n,r,d,s=0;cin>>n>>r;
    if(n<10)
    {
      d=100*(10-n);
      s=r+d;
      cout<<s;
    }
    else
    cout<<r;}

Measured memory_bytes: 256
import sys

word=input()

front = int(word[0:2])
back  = int(word[2:4])

# チェックするのはMMだけでよい

f = (1 <= front <= 12)
b = (1 <= back <= 12)

if f == True:
	if b == True:
		print('AMBIGUOUS')
	else:
		print('MMYY')
else:
	if b == True:
		print('YYMM')
	else:
		print('NA')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int INF=INT_MAX,MOD=1e9+7;

int main(){
	int dx[8]={0,1,1,1,0,-1,-1,-1};
	int dy[8]={-1,-1,0,1,1,1,0,-1};
	int h,w;
	while(cin>>h>>w&&h){
		char c[h][w]; rep(i,h)rep(j,w) cin>>c[i][j];
		vector<string> s;
		for(int y=0;y<h;y++){
			for(int x=0;x<w;x++){
				for(int dir=0;dir<8;dir++){
					int nowy=y,nowx=x;
					string tmp;
					while(1){
						tmp+=c[nowy][nowx];
						nowy=(h+nowy+dy[dir])%h;
						nowx=(w+nowx+dx[dir])%w;
						s.push_back(tmp);
						if(nowy==y&&nowx==x) break;
					}
				}
			}
		}
		sort(s.begin(),s.end());
		string ans="0"; int size=1;
		for(int i=0;i<(int)s.size()-1;i++){
			//cout<<s[i]<<endl;
			string tmp;
			if(s[i]==s[i+1]){
				tmp=s[i];
			}
			if(size<(int)tmp.size()){
				ans=tmp;
				size=tmp.size();
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}



Measured memory_bytes: 31304
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
 	cin.tie(NULL);	
	int n;
	cin>>n;

	int a[n];
	for(int i=0;i<n+1;i++)
		{
			cin>>a[i];
		}
		int b[n-1];
		for(int i=0;i<n;i++)
		{
			cin>>b[i];
		}
	long long sum=0;
	for(int i=0;i<n;i++)
	{
		if(b[i]>a[i])
		{
			sum+=a[i];
			b[i]-=a[i];
			int total=min(b[i],a[i+1]);
			sum+=total;
			a[i+1]=a[i+1]-total;
		}
		else
		{
			sum+=b[i];
		}

	}
	cout<<sum;

}

Measured memory_bytes: 1024
import java.io.*;
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args)throws IOException{
		InputStreamReader is = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(is);
		
		
		while(true){
		String str = br.readLine();
		if(str==null)break;
		int n = Integer.parseInt(str);
		int count = 0;
		for(int a = 0; a < 10; a++){
			for(int b = 0; b < 10; b++){
							
			for(int c = 0; c < 10; c++){
				
				
			for(int d = 0; d < 10; d++){
				if(a+b+c+d == n)
					count++;
			}}	
			}	
			
		}
		System.out.println(count);
	}

}
}

Measured memory_bytes: 9456
#include <cstdio>
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

const int inf=1<<20;
int d[100010];

int main(void){
	int n,m,p;
	cin >> n >> m >> p;
	for(int i=0;i<m;++i) cin >> d[i];
	sort(d,d+m);
	int ans=inf;
	for(int i=0;i<m;++i){
		int a=d[i],b=d[(i+1)%m];
		if( (a<=b&&a<=p&&p<=b)||(b<=a&&(p<=b||a<=p)) ){
			int left=p-a,right=b-p;
			if(left<0) left+=n;
			if(right<0) right+=n;
			ans=min(ans,n-left);
			ans=min(ans,n-right);
		}else{
			int left=a-p,right=p-b;
			if(left<0) left+=n;
			if(right<0) right+=n;
			ans=min(ans,2*left+right);
			ans=min(ans,left+2*right);
		}
	}
	cout << ans*100 << endl;
	return 0;
}

Measured memory_bytes: 1212
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	int k;
	cin>>k;
	char c=s[k-1];
	for(int i=0;i<n;i++)
	{
		if(s[i]==c)
		{
			cout<<c;
		}
		else
		cout<<"*";
	}
	cout<<endl;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=a;i<=n;++i)
#define lpd(i,a,n) for(int i=a;i>=n;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 52;
int n,a[N],b[N];
bool fail,vis[N];
vi v;

bool dfs(int i, int j, int r){
    vis[i] = true;
    if(i == j) return true;
    lp(x,1,r) if(!vis[i%x] and dfs(i%x, j, r)) return true;
    for(int x : v) if(!vis[i%x] and dfs(i%x, j, r)) return true;
    return false;
}

bool check(int i){
    lp(j,1,n){
        mem(vis, 0);
        if(!dfs(a[j], b[j], i)) return false;
    }
    return true;
}

int main(){
    readi(n);
    lp(i,1,n) readi(a[i]);
    lp(i,1,n) readi(b[i]), fail |= b[i] > a[i];
    if(fail) return cout <<-1, 0;

    ll ans = 0;
    lpd(i,51,1){
        if(check(i-1)) continue;
        else if(check(i)) v.pb(i), ans += 1ll << i;
        else return cout <<-1, 0;
    }

    cout <<ans;
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,mod=1e9+7;
#define ll long long

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int a,b;
    cin>>a>>b;
    for(int i=1;i<N;i++)
    {
        if(i*8/100==a&&i*10/100==b)
            return cout<<i<<endl,0;
    }
    cout<<-1<<endl;
    return 0;
}


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

int main(){
  int n;cin>>n;
  int a;
  vector<ll> x(n+1,0);
  rep(i,n){
    cin>>a;
    x[i+1]=x[i]+a;
  }
  ll mn=1e18,y;
  rep(i,n-1){
    y=x[n]-x[i+1];
    mn=min(mn,abs(x[i+1]-y));
  }
  cout<<mn;
}

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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 998244353;



int main() {

	int n;
	cin >> n;
	n--;
	cout << n / 2 << endl;

}

Measured memory_bytes: 764