akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

#define next '\n'
#define sp " "
#define print(x) cout << (x)
#define println(x) cout << (x) << next
#define stop return(0)
#define rep(i, n) for(int (i) = (0); (i) < (n); (++i))
#define FOR(i, start, end) for(int (i) = (start); (i) < (end); (++i))
#define foreach(e, elem) for(auto& (e) : (elem))
#define FAST ios::sync_with_stdio(false); cin.tie(nullptr)
#define size(s) (s).size()
#define all(vec) (vec).begin(), (vec).end()
using ll = long long;
using ull = unsigned long long;

int k;
ll sum = 0;

ll gcd(ll a, ll b){
    if(a < b) std::swap(a, b);

    ll result = b;
    while(a % result != 0){
        result = a % b;
        a = b;
        b = result;
    }

    return result;
}

int main() {
    FAST;

    cin >> k;

    for(int i = 1; i <= k; ++i){
        for(int j = 1; j <= k; ++j){
            ll ab = gcd(i, j);
            for(int l = 1; l <= k; ++l){
                ll abc = gcd(ab, l);
                sum += abc;
            }
        }
    }

    println(sum);
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
#define REP(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for(ll (i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for(ll (i) = (m); (i) < (n); (i)++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define _GLIBCXX_DEBUG

template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;

const double PI = 3.14159265358979323846;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int main()
{	
    string s;
    cin >> s;
    ll ans = 0;
    ll j = 0;

    REP(i, s.length()){
        if(s[i] == 'W'){
            ans += i - j;
            j++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ll n;
  cin>>n;
  ll ans;
  ans=n/500;
  n-=ans*500;
  ans*=1000;
  ans+=n/5*5;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3588
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
dic={}
for i in range(H):
    for j in range(W):
        dic[A[i][j]]=(i,j)
dist=[0]*(H*W+10)
for i in range(D+1,H*W+1):
    xd=abs(dic[i][0]-dic[i-D][0])
    yd=abs(dic[i][1]-dic[i-D][1])
    dist[i]=dist[i-D]+xd+yd
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    print(dist[R]-dist[L])

Measured memory_bytes: 66676
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

template <class T1, class T2>
ostream& operator << (ostream& out, pair <T1, T2> p)
{
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}

template <class T1, class T2>
istream& operator >> (istream& in, pair<T1, T2> &p)
{
	in >> p.first >> p.second;
	return in;
}

template <class T>
istream& operator >> (istream& in, vector<T> &v)
{
	for (T &x : v)
		in >> x;
	return in;
}

template <class T>
ostream& operator << (ostream& out, vector<vector<T>> &v)
{
	for (vector<T> &x : v)
		out << x << '\n';
	return out;
}

template <class T>
ostream& operator << (ostream& out, vector<T> &v)
{
	for (T &x : v)
		out << x << ' ';
	return out;
}

long long gcd (long long a, long long b)
{
	if (b > a)
		swap(a, b);
	return (b ? gcd(b, a % b) : a);
}

using ll   = long long;
using pii  = pair<int, int>;
using pll  = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi   = vector<int>;
using vl   = vector<long long>;
using vvi  = vector<vector<int>>;
using vvl  = vector<vector<long long>>;

#define F          first
#define S          second
#define First      first.first
#define Second     first.second
#define Third      second
#define mp         make_pair
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define per(i,b,a) for (int i = (b); i > (a); i--)
#define all(x)     x.begin(), x.end()
#define ret(x)     return cout << x, 0;
#define throwex    throw runtime_error ("Found the error.");

const int h = 1000000007;

signed main()
{
	ios::sync_with_stdio(false);
	#ifdef ONLINE_JUDGE
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.setstate(ios::failbit);
	#endif

	int k;
	cin >> k;
	ll ans = 0;
	rep(i,1,k+1)
		rep(j,1,k+1)
			rep(z,1,k+1)
				ans += gcd(gcd(i, j), z);
	cout << ans;
}


Measured memory_bytes: 3648
n = int(input())
H = list(map(int, input().split()))

for i in reversed(range(n-1)):
    if H[i] <= H[i+1]:
        continue
    elif H[i]-1 == H[i+1]:
        H[i] -= 1
    else:
        break
else:
    print('Yes')
    exit(0)
print('No')


Measured memory_bytes: 14396
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part
from collections import deque
 
n, m =MI()
 
ans = [-1 for _ in range(n+1)]


ans[0] = 0
ans[1] = 0
 
V = [[] for _ in range(n+1)]
 
for _ in range(m):
    x, y = MI()
    V[x].append(y)
    V[y].append(x)
 
d = deque([1])
 
while d:
    l = d.popleft()
    for v in V[l]:
        if ans[v] != -1:
            continue
        ans[v] = l
        d.append(v)
        
 
    
if ans.count(-1) > 0:
    print('No')
else :
    print('Yes')
    for i in ans[2:]:
        print(i)

Measured memory_bytes: 34732
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define all(c) begin(c),end(c)
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
//最大公約数
ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}
//最小公倍数
ll lcm(ll x, ll y) {
  return x/gcd(x, y)*y;
}
//素因数分解
vector<pair<ll,int>> factorize(ll n) {
  vector<pair<ll,int>> res;
  for (ll i = 2; i*i <= n; ++i) {
    if (n%i) continue;
    res.emplace_back(i,0);
    while (n%i == 0) {
      n /= i;
      res.back().second++;
    }
  }
  if (n != 1) res.emplace_back(n,1);
  return res;
}
 
 
 
 
int main() {
  int n;
  cin>>n;
  int d[n];
  rep(i,n){
    cin>>d[i];
  }
  int ans=0;

  rep(i,n){
    for(int j=i+1;j<n;j++){
      int a=d[i]*d[j];
      ans+=a;
    }
  }
  cout<<ans;
}




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

string str;

int evaluate(int idx){
  if(str[idx]=='('){
    int depth=1;
    int idx2=idx+1;
    while(depth>0){
      if(str[idx2]=='('){
        depth++;
      }else if(str[idx2]==')'){
        depth--;
      }else if(str[idx2]=='+' && depth==1){
        return max(evaluate(idx+1), evaluate(idx2+1));
      }else if(str[idx2]=='*' && depth==1){
        return min(evaluate(idx+1), evaluate(idx2+1));
      }
      idx2++;
    }
  }else{
    if(str[idx]=='-'){
      return 2-evaluate(idx+1);
    }else{
      return str[idx]-'0';
    }
  }
  return 0;
}

int main(){
  while(1){
    string tmp;
    cin >> tmp;
    if(tmp[0] == '.') break;

    str = tmp;
    int count = 0;
    for(int i=0; i<=2; i++){
      for(int j=0; j<=2; j++){ 
        for(int k=0; k<=2; k++){
          //substitute
          for(int idx=0; idx<(int)tmp.length(); idx++){
            if(tmp[idx]=='P') str[idx]='0'+i;
            else if(tmp[idx]=='Q') str[idx]='0'+j;
            else if(tmp[idx]=='R') str[idx]='0'+k;
            else str[idx]=tmp[idx];
          }
          if(evaluate(0) == 2) count++;
        }
      }
    }
    cout << count << endl;
  }
  return 0;
}

Measured memory_bytes: 3048
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

    ll k,x;cin>>k>>x;
    if(500*k>=x) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
import sys

def test():

	state = 0

	for inputs in sys.stdin:

		if state == 0:
			n = int(inputs)
			if n == 0:
				break
			state = 1
		else:
			score_array = list(map(int,inputs.split()))

			m = 0.0
			for score in score_array:
				m += score
			m = m / n

			sigma = 0.0
	
			for score in score_array:
				sigma += (score-m)**2/n
			sigma = sigma**0.5
			print(sigma)
			
			state = 0


if __name__ == "__main__":
	test()


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

int main(void) {
ll N;
cin >> N;
vector<ll> vec(N+1);
map<ll,ll> b,c;
for(ll i = 1;i <= N;i++) {
    cin >> vec.at(i);
    if (b.count(vec.at(i))) b[vec.at(i)]++;
    else b[vec.at(i)] = 1;
}
ll ans = 0;
for (ll i = 1;i <= N;i++) {
    if (b.count(i) && b[i] > 1)  ans += b[i] * (b[i]-1) / 2;
}
for (ll i = 1;i <= N;i++) {
    if (b[vec.at(i)] > 1) {
        cout << ans - b[vec.at(i)]+1 << endl;
    } else cout << ans << endl;
}

return 0;
}





Measured memory_bytes: 12756
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int n,m;
int money[100];
char ptn[100][10],in[10];

int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		rep(i,n)scanf("%s%d",ptn[i],money+i);
		
		int ans=0;
		rep(i,m)
		{
			scanf("%s",in);
			rep(j,n)
			{
				int k=7; for(;k>=0;k--)
				{
					if(ptn[j][k]=='*')
					{
						k=-1; break;
					}
					if(ptn[j][k]!=in[k])break;
				}
				if(k<0)
				{
					ans+=money[j]; break;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.*;
 
public class Main {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Map<List<Integer>, Integer> map = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            List<Integer> p = conv(i);
            map.put(p, map.getOrDefault(p, 0)+1);
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            List<Integer> p = conv(i);
            List<Integer> q = new ArrayList<>();
            q.add(p.get(1));
            q.add(p.get(0));
            ans += map.getOrDefault(q, 0);
        }

        System.out.println(ans);
    }

    private static List<Integer> conv(int x) {

        int b = x%10;
        int a = x;
        while (x > 0) {
            a = x;
            x /= 10;
        }

        List<Integer> list = new ArrayList<>();
        list.add(a);
        list.add(b);

        return list;
    }
}


Measured memory_bytes: 46592
#include<stdio.h>
int main(void) {
	int N, count = 0;
	int i;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		if ((1 <= i && i <= 9) || (100 <= i && i <= 999) || 10000 <= i && i <= 99999) {
			count += 1;
		}
	}
	printf("%d", count);
	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1e+9;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


int N,M,Q;
vector<int> a,b,c,d;
int ans;

void dfs(vector<int> A) {
  if(A.size() == N+1) {
    int score = 0;
    rep(i,Q) {
      if(A[b[i]] - A[a[i]] == c[i]) score+=d[i];
    }
    ans = max(ans,score);
    return;
  }

  A.push_back(A.back());
  while(A.back() <= M) {
    dfs(A);
    A.back()++;
  }
  
  
}

int main() {
  cin >> N >> M >> Q;
  a=b=c=d=vector<int>(Q);
  rep(i,Q) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
  dfs(vector<int>(1,1));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3152
#include<stdio.h>

int nextInt();
void sort(int *a, int size);

int N, i;
int A[100000], B[100000], C[100000];
long long int a, b;

int main(){
	N=nextInt();
	for(i=0; i<N; i++){
		A[i]=nextInt();
		B[i]=nextInt();
		C[i] = A[i] + B[i];
		b += B[i];
	}
	sort(C, N);
	for(i=0; i<N; i+=2){
		a += C[i];
	}
	printf("%lld\n", a-b);
	return 0;
}

int nextInt(){
	int f=0; char c=getchar();
	while((c<'0')||('9'<c)){c=getchar();}
	while((c>='0')&&(c<='9')){f=f*10+(c-'0'); c=getchar();}
	return f;
}

char compare(int *x, int *y){
	return *x > *y;
}

int* med3(int *x, int *y, int *z){
	if(compare(x, y)){
		if (compare(y, z)){return y;}else if(compare(z, x)){return x;}else{return z;}
	} else {
		if (compare(z, y)){return y;}else if(compare(x, z)){return x;}else{return z;}
	}
}

void quickSort(int *left, int *right){
	if(left >= right){return;}
	int *pivot = med3(left, left+(right-left)/2, right);
	int *l=left, *r=right;
	int t;
	while(1){
		while (compare(l, pivot)){l++;}
		while (compare(pivot, r)){r--;}
		if(l>=r){break;}
		t=*l; *l=*r; *r=t;
		if(pivot == l){
			pivot = r;
		}else if(pivot == r){
			pivot = l;
		}
		l++; r--;
	}
	quickSort(left, l-1);
	quickSort(r+1, right);
}

void sort(int *a, int size){
	quickSort(a, a+size-1);
}


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

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF * 300 * 300;
const int MOD = 1e9+7;

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

LL modpow(LL a, LL n) {
    LL res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

LL modinv(LL a) {
    LL b = MOD, u = 1, v = 0;
    while (b) {
        LL t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return u;
}

LL moddev(LL a, LL b){
	return a * modinv(b) % MOD;
}

void Main()
{
    int k,x;
    cin >> k >> x;
    if(500*k >= x){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main() {

  int N;
  int A;
  int B;

  std::cin >> N;
  if (N == 2) {
    std::cin >> A;
    std::cin >> B;

    std::cout << A + B << std::endl;
    return 0;
  }

  std::cout << "Hello World" << std::endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] a = new int[2][n];

		for(int i = 0; i < 2; i++) {
			for (int j = 0; j < n; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		int max = 0;
		for (int i = 0; i < n; i++){
			int checksum = 0;
			for (int j = 0; j < n; j++) {
				if (j == i) {
					checksum += a[0][j] + a[1][j];
				} else if (j < i) {
					checksum += a[0][j];
				} else {
					checksum += a[1][j];
				}
			}
			max = Math.max(max, checksum);
		}
		System.out.println(max);



	}

}


Measured memory_bytes: 23764
#!/usr/bin/env python3
import sys
import math


def solve(A: int, B: int):

    result = 100000
    count = 0
    for i in range(1, 10000 + 1):
        if math.floor(i * 0.08) == A and math.floor(i * 0.1) == B:
            result = min(result, i)
            count += 1
    if count == 0:
        print(-1)
    else:
        print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
import sys
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,m=MI()
	li=[LI() for _ in range(m)]

	li.sort(key=lambda x:x[1])
	#print(li)

	now=0
	ans=0

	for a,b in li:
		if now<=a:
			now=b
			ans+=1
	print(ans)

























if __name__ == "__main__":
	main()


Measured memory_bytes: 28660
n = int(input())
a = [int(i) for i in input().split()] 
ls = a

st = int(n/2)
ans =  [i+st+1 for i, n in enumerate(a[st:]) if n ==1] 
for ind in range(st, 0, -1):
    tmp = [ls[i] for i in range(2*ind-1, n, ind)]
    s = sum(tmp)%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        ans.append(ind)
        
print(sum(ls))
print(' '.join(map(str, ans)))

Measured memory_bytes: 21324
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  int r = 0, b = 0;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == 'R')r++;
    else b++;
  }
  if(r > b)cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
# D - Banned K
from collections import Counter


def main():
    N, *A = map(int, open(0).read().split())
    counter = Counter(A)
    total = 0
    dif = {}
    for k, v in counter.items():
        total += max(0, v * (v - 1) // 2)
        dif[k] = max(0, v - 1)
    ans = [total - dif[a] for a in A]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left!=NIL)x=x->left;
  return x;
}

Node treeMaximum(Node x){
  while(x->right!=NIL)x=x->right;
  return x;
}

Node treeSearch(Node u, int k){
  if(u==NIL||k==u->key)return u;
  if(k<u->key)
    return treeSearch(u->left,k);
  else
    return treeSearch(u->right,k);

}

Node treeSuccessor(Node x){
  Node y=x->parent;
  if(x->right!=NIL)
    return treeMinimum(x->right);
  while(y!= NIL&&x==y->right){
    x=y;
    y=y->parent;
  }
  return y;

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z->left==NIL || z->right==NIL)y=z;
  else y=treeSuccessor(z);
  
  if(y->left!=NIL)x=y->left;
  else x=y->right;

  if(x!=NIL)x->parent=y->parent;
  
  if(y->parent==NIL)root=x;
  else if(y==y->parent->left)y->parent->left=x;
  else y->parent->right=x;

  if(y!=z)z->key=y->key;
  
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  
  while(x!=NIL){
    y=x;
    if(z->key<x->key)x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL)root=z;
  else if(z->key<y->key)y->left=z;
  else y->right=z;
  
}

void inorder(Node u){
  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 25140
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	for (int b, r, g, c, s, t; cin >> b >> r >> g >> c >> s >> t && (b || r || g || c || s || t);) {
		int coin = 100;
		coin += b * 15;
		coin += b * 15 * 5;
		coin += r * 15;
		coin += r * 3 * 15;
		coin += g * 7;
		coin += c * 2;
		coin -= (t - s - b * 5 - r * 3) * 3;
		coin -= (b * 5 + r * 3) * 2;
		cout << coin << endl;
	}
	return 0;
}

Measured memory_bytes: 3072
#!/usr/bin/env python3
#AGC31 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
c = [I() for _ in range(n)]
dp1,dp2 = [0]*(n+1),[0]*(max(c)+1)
dp1[0] = 1
for i in range(n):
    if dp2[c[i]] == 0:
        dp1[i+1] = dp1[i]
        dp2[c[i]] = dp1[i]
        dp2[c[i]] %= mod
    else:
        if c[i] == c[i-1]:
            dp1[i+1] = dp1[i]
            continue
        dp1[i+1] += dp2[c[i]]
        dp1[i+1] += dp1[i]
        dp2[c[i]] += dp1[i]
        dp2[c[i]] %= mod
        dp1[i+1] %= mod
print(dp1[-1] % mod)


Measured memory_bytes: 54364
/*
 * Problem Description: Graph II - Minimum Spanning Tree
 * Category: Graph
 * Author: Khan
 * Date: 22th October, 2017
 */

#include <iostream>

using namespace std;

static const int MAX = 1000;
static const int INF = (1 << 21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim()
{
    int u, minv;
    int d[MAX], p[MAX], color[MAX];

    for (int i = 0; i < n; ++i)
    {
        d[i] = INF;
        p[i] = -1;
        color[i] = WHITE;
    }

    d[0] = 0;

    while(true)
    {
        minv = INF;
        u = -1;
        for (int i = 0; i < n; ++i)
        {
            if(minv > d[i] && color[i] != BLACK)
            {
                u = i;
                minv = d[i];
            }
        }
        if(u == -1)
            break;
        color[u] = BLACK;
        for (int v = 0; v < n; ++v)
        {
            if(color[v] != BLACK && M[u][v] != INF)
            {
                if(d[v] > M[u][v])
                {
                    d[v] = M[u][v];
                    p[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }

    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        if(p[i] != -1)
            sum += M[i][p[i]];
    }
    return sum;
}

int main(int argc, char const *argv[])
{
    //freopen("sample.txt", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            int e; cin >> e;
            M[i][j] = (e == -1) ? INF : e;
        }
    }
    cout << prim() << endl;
    return 0;
}

Measured memory_bytes: 3488
import java.util.HashMap;
import java.util.Scanner;
public class Main
{
    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        System.out.println(map.keySet().size());
    }




}

Measured memory_bytes: 77032
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
  int n,a,mini,ans=-(1<<30);
  scanf("%d %d",&n,&mini);
  for(int i=0;i<n-1;i++){
    scanf("%d",&a);
    if(a-mini>ans)ans=a-mini;
    if(mini>a)mini=a;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3220
#include<stdio.h>
#include<string.h>
#include<stdlib.h>


int n,q;


//Aのｋ番目（0〜n-1）以降の要素をつかって、Mを作れるかを判定。成功：１　失敗:０
int judge(int *A,int M,int k){
  if(k==n-1){
    if(A[k]==M) return 1;
    else return 0;
  }
  else{
    if(M <A[k]) return judge(A,M,k+1);
    else if(M==A[k]) return 1;
    else{
      if(judge(A,M-A[k],k+1)==1 || judge(A,M,k+1)==1) return 1;
      else return 0;
    }
  }
}
  



int main(){
  int *A;
  int M;
  int i,j;
  
  scanf("%d",&n);
  A=malloc(n*sizeof(int));
  for(i=0;i<n;i++){
    scanf("%*[ \n]%d",&A[i]);
  }

  int max;
  int cha;
  for(i=0;i<n-1;i++){
    max=i;
    for(j=i+1;j<n;j++){
      if(A[max] <A[j]) max=j;
    }
    cha=A[max];
    A[max] =A[i];
    A[i]=cha;
  }//降順にソート

  
  scanf("%*[ \n]%d",&q);
  for(i=0;i<q;i++){
    scanf("%*[ \n]%d",&M);
    if(judge(A,M,0)==1) printf("yes\n");
    else printf("no\n");
  }
  return 0;
}




    


Measured memory_bytes: 2108
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    r = I()

    print(3 * r ** 2)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9936
# inputを高速化する。
import sys
import numpy as np

input = sys.stdin.readline

N,K = map(int, input().split())
blocks = list(map(int, input().split()))

route = np.zeros(N, dtype=int)

blocks = np.array(blocks)

for i in range(1, N):
    count = max(0, i-K)
    route[i] = min(route[count:i] + np.abs(blocks[count:i] - blocks[i]))

print(route[-1])

Measured memory_bytes: 22828
#include<bits/stdc++.h>
#define int long long
#define N 105
#define K 73140
#define P 1000000007
using namespace std;
int n,m,f[N][K],X[K],Y[K];
signed main(){
	scanf("%lld%lld",&m,&n);
	int x=1,y,res,tot=0;
	while(x<=m){
		res=m/x;
		y=m/res;
		X[++tot]=x,Y[tot]=y;
		x=y+1;
	}
	for(int i=1;i<=tot;i++)f[0][i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=tot;j++)
			f[i][j]=(f[i-1][tot-j+1]*(Y[j]-X[j]+1)%P+f[i][j-1])%P;
	printf("%lld\n",f[n][tot]);
	return 0;
}

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


int main() {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    int K;
    scanf("%d", &K);

    int m = max(A, max(B, C));
    int sum = A + B + C - m;
    for(int i = 0; i < K; i++) {
        m *= 2;
    }
    sum += m;
    printf("%d\n", sum);

    return 0;
}


Measured memory_bytes: 128
# include <iostream>
# include <sstream>
# include <cstdio>
# include <cstdlib>
# include <algorithm>
# include <string>
# include <cstring>
# include <cmath>
# include <stack>
# include <queue>
# include <vector>
# include <list>
# include <map>
# include <set>
# include <deque>
# include <iterator>
# include <functional>
# include <bitset>
# include <climits>
# include <ctime>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define odd(x) ((x)&1)
#define sqr(x) ((x)*(x))
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for (int i=(a); i<=(b); ++i)
#define rep_it(it,x) for (__typeof((x).begin()) it=(x).begin(); it!=(x).end(); it++)
#define ____ puts("\n_______________\n\n") 
#define debug(x) ____; cout<< #x << " => " << (x) << endl
#define debug_pair(x) cout<<"\n{ "<<(x).fir<<" , "<<(x).sec<<" }\n"
#define debug_arr(x,n) ____; cout<<#x<<":\n"; rep(i,0,n) cout<<#x<<"["<<(i)<<"] => "<<x[i]<<endl
#define debug_set(x) ____; cout<<#x<<": \n"; rep_it(it,x) cout<<(*it)<<" "; cout<<endl
#define debug_map(x) ____; cout<<#x<<": \n"; rep_it(it,x) debug_pair(*it)
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int oo = /*2 * 1000 * 1000 * 1000*/0x3f3f3f3f;
const int _cnt = 1000 * 1000 + 7;
const int _p = 1000 * 1000 * 1000 + 7;
const double PI=acos(-1);
const double eps=1e-9;
int o(int x) { return x%_p; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a, int b) { return a / gcd(a, b)*b; }

void file_put() {
    freopen("filename.in", "r", stdin);
    freopen("filename.out", "w", stdout);
}

int n,m,x,y;
vector <int> V[200005];
bool v[200005];

void dfs(int k,int s){
	if (s>2) return ;
	v[k]=1;
	for (auto it: V[k]) {
		if (v[it]) continue;
		dfs(it,s+1);
	}
} 

int main() {
    //file_put();
    
    scanf("%d%d",&n,&m);
	rep(i,1,m) {
		scanf("%d%d",&x,&y);
		V[x].pb(y);
		V[y].pb(x);
	} 
	memset(v,0,sizeof(v));
	dfs(1,0);
	if (v[n]) printf("POSSIBLE\n"); else printf("IMPOSSIBLE\n");
	
    return 0;
}

Measured memory_bytes: 12144
#include <iostream>
using namespace std;
int main()
{
  long int n;
  cin>>n;
  long long int sum=0;
  for(long int i=1;i<=n;i++)
  {
    if((i%3!=0)&&(i%5!=0))
    sum=sum+i;
  }
  cout<<sum<<"\n";
}

Measured memory_bytes: 3628
import java.io.*;
import java.util.Arrays;
 
class Main
{
    public static void main (String[ ] args) throws Exception
    {
        BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
        StringBuilder sb = new StringBuilder();
        int[][][] room = new int[4][3][10];
         
        int n = Integer.parseInt(br.readLine());
 
        for(int i = 0; i < n; i++)
        {
            String[] strArr = (br.readLine()).split(" ");
            int b = Integer.parseInt(strArr[0]);
            int f = Integer.parseInt(strArr[1]);
            int r = Integer.parseInt(strArr[2]);
            int v = Integer.parseInt(strArr[3]);
             
            room[b-1][f-1][r-1] += v;
        }
         
        for(int i = 0; i < 4; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                for(int k = 0; k < 10; k++)
                {
                    sb.append(" ").append(room[i][j][k]);
                }
                sb.append("\n");
            }
            if(i != 3)
            {
                sb.append("####################\n");
            }
        }
        System.out.print(sb);
    }
}

Measured memory_bytes: 24656
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int n,m;
    cin >> n;
    vector<string> s(n);
    rep(i,n) cin >> s[i];
    cin >> m;
    vector<string> t(m);
    rep(i,m) cin >> t[i]; 
    int ans = 0;
    rep(i,n) {
        int cnt = 0; string S = s[i];
        for (int j = 0; j < n; j++)
        {
            if (s[i] == s[j])
            {
                cnt++;
            }
        }
        for (int j = 0; j < m; j++)
        {
            if (s[i] == t[j]) {
                cnt--;
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <functional>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// #define int long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int nINF = 1<<31;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<char, int> pci;

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

const int N = 1e5+10;
int n, k = 2, h[N];
ll dp[N];

signed main() {
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);
    fill(dp, dp+N, INF);
    dp[1] = 0;
    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) {
    	FOR(j, 1, k) {
    		if(i+j > n) break;
    		dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]));
    	}
    }
    cout << dp[n] << endl;

    return 0;
}

// Easy things to check:
// - LONG LONGS (WA)
// - const int N is correct (WA, RTE)
// - .size()-k underflow (WA, RTE, TLE)
// - small n edge cases (WA)

// Rare mistakes made in the past:
// - division by 0 (WA)
// - integer division (WA)
// - setprecision (WA)
// - INF not big enough using ll (WA)
// - setting min to 0 instead of -INF (WA)
// - outputting debug (WA)
// - allocating too much memory (locRTE, MLE)
// - stack size (locRTE)


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pull = pair<ull, ll>;
#define INF 1000000000
#define LLINF 10000000000000000ll
#define MOD 1000000007LL

bool dbgflag = false;

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

  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  bool check = true;
  /*for (int i = 0; i < n; i++) {
    if (a[i] != 0) {
      check = false;
      break;
    }
  }
  if (check) {
    for (int i = 0; i < n; i++) {
      cout << 0;
      if (i != n-1) cout << ' ';
      else cout << endl;
    }
    return 0;
  }*/

  vector<ll> sum(n+1);
  for (int i = 0; i < k; i++) {
    for (int j = 0; j <= n; j++) sum[j] = 0;
    for (int j = 0; j < n; j++) {
      sum[max(0LL, j - a[j])]++;
      sum[min(n, j + a[j] + 1)]--;
    }
    a[0] = sum[0];
    check = true;
    for (int j = 1; j < n; j++) {
      a[j] = a[j-1] + sum[j];
      if (check && a[j] != n) check = false;
    }
    if (check) break;
  }
  if (check) {
    for (int i = 0; i < n; i++) {
      cout << n;
      if (i == n-1) cout << endl;
      else cout << ' ';
    }
    return 0;
  }

  else {
    for (int i = 0; i < n; i++) {
      cout << a[i];
      if (i == n-1) cout << endl;
      else cout << ' ';
    }
    return 0;
  }

}


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

int n, m, ans, s[55];
bool a[55][55];
void f(int p) {
	int i;
	if (s[p] == 1) {
		ans++;
		for (i =1; i <= n; i++) {
			if (a[p][i] == 1) break;
		}
		a[p][i] = a[i][p] = 0;
		s[p]--;
		s[i]--;
		f(i);
	}
}
int main()
{
	int i ,j, t1, t2;
	cin >> n >> m;
	while (m--) {
		scanf ("%d %d", &t1, &t2);
		a[t1][t2] = a[t2][t1] = 1;
		s[t1]++;
		s[t2]++;
	}
	for (i = 1; i <= n; i++) {
		f(i);
	}
	cout << ans;
    return 0;
}


Measured memory_bytes: 256
"""
author : halo2halo
date : 24, Jan, 2020
"""

import sys
import itertools

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N=readline().decode('utf8')
S=N[:3]+'8'+N[4:]
print(S)


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

int main() {
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int mx = k + a[0] - a[n - 1];
    for (int i = 0; i < n - 1; i++) {
        mx = max(mx, a[i + 1] - a[i]);
    }
    cout << k - mx << endl;
    return 0;
}


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

class Program {
    static string ReadLine() { return Console.ReadLine(); }
    static int ReadInt() { return int.Parse(ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }

    static void Main() {
        ReadInt();
        var xs = ReadInts();
        Array.Sort(xs);
        int ans = 0;
        for (int i = 0; i < xs.Length; i += 2) {
            ans += xs[i];
        }
        Console.WriteLine(ans);
    }
}

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

using namespace std;

int N, K;
int arr[200005];
map<int, int> mp;

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    for(int i = 1; i<=N; i++){
        cin >> arr[i];
        arr[i] += K-1;
        arr[i] %= K;
        arr[i] += arr[i-1];
        arr[i] %= K;
    }
    long long ans = 0;
    for(int r = 0, l = r-K+1; r<=N; r++, l++){
        ans += mp[arr[r]];
        mp[arr[r]]++;
        if(l >= 0){
            mp[arr[l]]--;
        }
        //cout << ans << " " << r << endl;
    }
    cout << ans << endl;
}


Measured memory_bytes: 10368
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define F first
#define S second
#define db double
#define pb push_back
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
using namespace std;

set<char> st={'a','e','i','o','u'};

// ll mod=1e9 +7;
ll mod=  998244353;

const int M=200006;
int f[M],inv[M];
int expo(int base,int exponent,int mod){
    int ans=1;
    while(exponent!=0){
        if(exponent&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exponent>>=1;
    }
    return ans%mod;
}
void compute(){
    f[0]=1;
    rep(i,1,M-1){
        f[i]=(1LL*i*f[i-1])%mod;
    }
    inv[M-1]=expo(f[M-1],mod-2,mod);
    for(int i=M-2;i>=0;i--){
        inv[i]=(1LL*(i+1)*inv[i+1])%mod;
    }
}
int C(int n,int r){
    return (1LL*((1LL*f[n]*inv[r])%mod)*inv[n-r])%mod;
}




int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    compute();
    
    ll tests=1;
   // cin>>tests;
    while(tests--)
    {
      ll n,m;
      cin>>n>>m;
      cout<<C(n,2) + C(m,2);


    }
    
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    int n, d;
    cin >> n >> d;
    vector<int> x(n * d);
    rep(i, n * d) cin >> x[i];
    
    int c = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            ll diff = 0;
            rep(k, d) {
                ll dx = x[d * i + k] - x[d * j + k];
                diff += dx * dx;
            }
            int sq = (int)sqrt(diff);
            if (sq * sq == diff) {
                c += 1;
            }
        }
    }
    put(c)

    return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;

int main()
{
ll n,m;
cin >> n>>m;
ll t[n] = {};
rep(i, m){
    cin >> t[i];
}
ll co=0;
ll dp[n+1]={};
//初期
dp[0]=1;
if(t[0]==1){
  co++;
}
else{
  dp[1]=1;
}

//loop
for(ll i=2;i<=n;i++){
  if(i==t[co]){
    co++;
    continue;
  }
  dp[i]=dp[i-1]+dp[i-2];
  dp[i]%=mo;
}
cout << dp[n] << endl;
return 0;
}

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

using namespace std;

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

    int s = 0;
    for(int i=0;i<=100;i++){
        s+=a;
        if(s%b==c){
            cout<<"YES";
            return 0;
        }
    }
    cout<<"NO";
}


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

template <class T, class U>
inline bool chmax(T& t, const U& f) { return t < f ? t = f, true : false; }

int solve(int N, const vector<int>& L, const vector<int>& D) {
    vector<int> mem(1 << 16, -1);
    function<int(int)> dfs = [&](int S) {
        int& t = mem[S];
        if (t != -1) return t;
        t = 0;
        rep(i, N) if ((S & D[i]) == D[i]) chmax(t, L[i] + dfs(S - D[i]));
        return t;
    };
    return dfs((1 << 16) - 1);
}

int main() {
    for (int N; cin >> N, N;) {
        vector<int> L(N), D(N);
        rep(i, N) {
            int M; cin >> M >> L[i];
            while (M--) {
                int S, E; cin >> S >> E;
                D[i] |= -1 & (1 << (E - 6)) - 1 ^ (1 << (S - 6)) - 1;
            }
        }
        cout << solve(N, L, D) << endl;
    }
}

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

int main() {
    int N, M, a, ans=0, flag=-1, tmp;
    cin  >> N;
    priority_queue<int, vector<int>> asc;
    priority_queue<int, vector<int>, greater<int>> desc;
    vector<int> ansX(N), ansY(N);
    

    for(int i=0; i<N; i++){
	cin >> a;
	desc.push(a);
	asc.push(a);
    }

    if(asc.top()<=0)
	flag = 1;
    else if(desc.top() >=0)
	flag = 2;
    else
	flag = 3;

    if(flag == 3){
	tmp = asc.top();
	asc.pop();    	
    }


    for(int i=0; i<N-1; i++){
	if(flag ==1){
	    ansX[i] = asc.top();
	    ansY[i] = desc.top();
	    a = asc.top() - desc.top() ;
	    	    
	    desc.pop();
	    asc.pop();
	    desc.push(a);
	    asc.push(a);


	}
	else if(flag == 2){
	    ansX[i] = desc.top();
	    ansY[i] = asc.top();
	    a = desc.top() - asc.top() ;
	    	    
	    desc.pop();
	    asc.pop();
	    desc.push(a);
	    asc.push(a);

	    
	}
	else{
	    
	}
    }
    if(flag == 3){
	for(int i=0; i<N-1; i++){
	    if(asc.top() > 0 && flag ==3){
		a = desc.top() - asc.top() ;				
		ansX[i] = desc.top();
		ansY[i] = asc.top();		
	    }
	    else{
		flag =1;
		asc.push(tmp);
		a = asc.top() - desc.top();
		ansX[i] = asc.top();
		ansY[i] = desc.top();


	    }
	    desc.pop();
	    asc.pop();
	    desc.push(a);
	    asc.push(a);

	}
    }


    if(flag == 2)
	swap(ansX[N-2], ansY[N-2]);
    
    ans =ansX[N-2] - ansY[N-2];
    cout << ans << endl;
    
    for(int i=0; i<N-1; i++){
	cout << ansX[i] << " "<< ansY[i] << endl;
    }    
}


Measured memory_bytes: 4080
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vector<double> p(n);
  for(int i=0;i<n;++i) {
    cin >> p[i];
  }
  vector<vector<double>> dp(n+1, vector<double>(3000, 0.0));
  dp[0][0] = 1.0;
  for(int i=0;i<n;++i) {
    for(int j=0;j<3000;++j) {
      dp[i+1][j+1] += dp[i][j] * p[i];
      dp[i+1][j] += dp[i][j] * (1.0 - p[i]);
    }
  }
  int st = (n%2 ? n/2+1 : n/2);
  double ans = 0.0;
  for(int i=st;i<=n;++i) {
    ans += dp[n][i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 70784