akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int r;
	cin >> r;
	if(r < 1200)
	{
		cout << "ABC";
	}
	else if(r < 2800)
	{
		cout << "ARC";
	}
	else
	{
		cout << "AGC";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1100;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
const int Log=40;
int p2[Log];
char mp[4]={'U','D','R','L'};
int n;
int x[maxn],y[maxn];
int Abs(int x)
{
	if(x<0) return -x;
	return x;
}
int check()
{
	for(int i=2;i<=n;i++)
	{
		if(Abs(x[i]+y[i])%2!=Abs(x[i-1]+y[i-1])%2) return 0;
	}
	return 1;
}
int Ch(int x,int y,int k)
{
	int d1=Abs(x+y);
	int d2=Abs(x-y);
	if(d1>k||d2>k) return 0;
	return 1;
}
void put(int X,int Y,int k,int id)
{
	if(k==-1) return;
	int d=p2[k]-1;
	for(int i=0;i<=3;i++)
	{
		int nx=X+dx[i]*p2[k],ny=Y+dy[i]*p2[k];
		if(!Ch(nx-x[id],ny-y[id],d)) continue;
		printf("%c",mp[i]);
		put(nx,ny,k-1,id);
		break;
	}
	return;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
	if(!check()) return printf("-1\n"),0;
	p2[0]=1;
	for(int i=1;i<=30;i++) p2[i]=p2[i-1]*2;
	int op=Abs((x[1]+y[1])%2);
	op^=1;
	printf("%lld\n",31+op);
	if(op) printf("1 ");
	for(int i=30;i>=0;i--) printf("%lld ",p2[i]);
	printf("\n");
	for(int i=1;i<=n;i++)
	{
		if(op) printf("R");
		put(op,0,30,i);
		printf("\n");
	}
	return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define yn(ans) cout<<(ans?"Yes":"No")<<endl
using namespace std;

int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> vec(n);
    for(int i=0;i<n;i++){
       scanf("%d",&vec[i]);
       if(i>=k){
         if(vec[i]>vec[i-k])printf("Yes\n");
         else printf("No\n");
       }
    }
}

Measured memory_bytes: 4056
N,K = map(int,input().split())
h = list(map(int,input().split()))
#print(h)
DP = [10**9]*N
DP[0] = 0
DP[1] = abs(h[1]-h[0])
for i in range(2,N):
    for j in range(max(i-K,0),i):
        DP[i] = min(DP[i], DP[j] + abs(h[i]-h[j]))
    #print(DP[i])
print(DP[-1])

Measured memory_bytes: 84392
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <list>
#include <cmath>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <vector>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
//cout << fixed << setprecision(17) << res << endl;
// const ll MOD = 1000000009;

#define M 1000000007

int main() {
    ll n;
    cin >> n;
    vector<ll> A(n);
    for (auto &a : A) {
        cin >> a;
    }
    vector<ll> B(n,0);
    ll count = 0;
    for (ll i = n; i > 0; --i) {
        ll c = 0;
        for (auto j = i; j <= n; j += i) {
            if (B[j-1] == 1) {
                ++c;
            }
        }
        if (c % 2 == A[i-1]) {
            B[i-1] = 0;
        } else {
            B[i-1] = 1;
            ++count;
        }
    }
    cout << count << endl;
    for (ll i = 0; i < n; ++i) {
        if (B[i] != 0) {
            cout << i+1 << " ";
        }
    }
    cout << endl;

    return 0;
err:
    cout << -1 << endl;
}


Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> picture(H);
  for ( int i = 0; i < H; i++ ) {
    cin >> picture.at(i);
  }
  
  for ( int i = 0; i < H+2; i++ ) {
    for ( int j = 0; j < W+2; j++ ) {
      if ( i == 0 || i == H + 1 || j == 0 || j == W + 1 ) {
        cout << "#";
      }
      else {
        cout << picture.at(i-1).at(j-1);
      }
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

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

    int N, M;
    cin >> N >> M;
    cout << (N == M ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
package main

import (
    "bufio"
    "os"
//    "strings"
    "strconv"
    "fmt"
)

const WIDTH = 502
const HEIGHT = 502

/*
var nrs = bufio.NewReaderSize(os.Stdin, 1000000)

func readLineToInt() []int {
    buf := make([]byte, 0, 1000000)
    for {
        l, p, e := nrs.ReadLine()
        if e != nil {
            panic(e)
        }
        buf = append(buf, l...)
        if !p {
            break
        }
    }
    line := strings.Split(string(buf), " ")
    var intLine []int
    for _, str := range line {
        n, _ := strconv.Atoi(str)
        intLine = append(intLine, n)
    }
    return intLine
}
*/

/*
var sc = bufio.NewScanner(os.Stdin)

func readLineToInt() []int {
    sc.Scan()
    line := strings.Split(sc.Text(), " ")
    var intLine []int
    for _, str := range line {
        n, _ := strconv.Atoi(str)
        intLine = append(intLine, n)
    }
    return intLine
}
*/

func scanInt(sc *bufio.Scanner) int {
    sc.Scan()
    v, _ := strconv.Atoi(sc.Text())
    return v
}

func main() {
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    var m, q int
    var l, r int
    var a, b int
    var mp [HEIGHT][WIDTH]int
    //nmq := readLineToInt()
    _, m, q = scanInt(sc), scanInt(sc), scanInt(sc)
    //sc.Scan()
    //fmt.Sscanf(sc.Text(), "%d %d %d", &n, &m, &q)


    for i := 0; i < m; i++ {
        //lr := readLineToInt()
        //l, r = lr[0], lr[1]
        //sc.Scan()
        //fmt.Sscanf(sc.Text(), "%d %d", &l, &r)
        l, r = scanInt(sc), scanInt(sc)
        mp[l][r] += 1
    }

    for x := 0; x < WIDTH - 1; x++ {
        mp[0][x] += mp[0][x + 1]
    }

    for y := 1; y < HEIGHT; y++ {
        for x := 0; x < WIDTH - 1; x++ {
            mp[y][x + 1] += mp[y][x]
            mp[y][x] += mp[y - 1][x]
        }
    }
    out := bufio.NewWriter(os.Stdout)
    for i := 0; i < q; i++ {
        //ab := readLineToInt()
        //a, b = ab[0], ab[1]
        //sc.Scan()
        //fmt.Sscanf(sc.Text(), "%d %d", &a, &b)
        a, b = scanInt(sc), scanInt(sc)
        fmt.Fprintln(out, mp[b][b] - mp[b][a - 1] - mp[a - 1][b] + mp[a - 1][a - 1])
    }
    out.Flush()
}

Measured memory_bytes: 6144
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

bool isPrime(ll n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
  
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
    return true; 
} 

ll power(ll x,ll y) 
{ 
	if(x == 0) 
        return 0; 
    if (y == 0) 
        return 1; 
    else if (y % 2 == 0) 
        return power(x, y / 2) * power(x, y / 2); 
    else
        return x * power(x, y / 2) * power(x, y / 2); 
} 

int main()
{
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif

    fastio
    ll t, i, j, n;
    cin>>n;
    string s;

    map<string, int> mp;
    for(i=0; i<n; i++)
    {
    	cin>>s;
    	mp[s]++;
    }
    cout<<"AC x "<<mp["AC"]<<"\n";
    cout<<"WA x "<<mp["WA"]<<"\n";
    cout<<"TLE x "<<mp["TLE"]<<"\n";
    cout<<"RE x "<<mp["RE"]<<"\n";
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
vector<int> G[55];
set<pair<int,int> > All;
int N,M,ptr,dest;
bool vis[55][55];
void dfs(int x,vector<pair<int,int> > E)
{
	if(x==dest&&!E.empty())
	{
		for(int i=0;i<E.size();i++)
			All.insert(E[i]);
		return ;
	}
	for(int i=0;i<G[x].size();i++)
		if(!vis[min(x,G[x][i])][max(x,G[x][i])])
		{
			vector<pair<int,int> > T=E;
			T.push_back(make_pair(min(x,G[x][i]),max(x,G[x][i])));
			vis[min(x,G[x][i])][max(x,G[x][i])]=true;
			dfs(G[x][i],T);
		}
	return ;
}
int main()
{
	cin>>N>>M;
	for(int i=0;i<M;i++)
	{
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=N;i++)
	{
		memset(vis,false,sizeof(vis));
		vector<pair<int,int> > T;
		dest=i;
		dfs(i,T);
	}
	cout<<M-All.size();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <cmath>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>
 
using namespace std;
 
 
int main() {
    long long a, b, x;
    cin >> a >> b >> x;
    if (a == 0)
    {
        cout << (b / x + 1) - 0 << endl;
    }
    else
    {
        cout << (b / x + 1) - ((a - 1) / x + 1) << endl;
    }
    
 
    return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  int AC = 0;
  int PE = 0;
  vector<pair<int, string>> sub(N, pair<int,string>(0,"WA"));
  vector<int> WA(N,0);
  for (int i = 0; i < N; i++) {
    sub[i].first = i;
  }
  
  for (int i = 0; i < M; i++) {
    int x;
    string s;
    cin >> x >> s;
    if (sub[x-1].second == "WA") {
      if (s == "WA") WA[x-1] += 1;
      if (s == "AC") {
        sub[x-1].second = "AC";
        AC += 1;
        PE += WA[x-1];
      }
    }
  }
  
  cout << AC << " " << PE << endl;
}

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

#define ll long long int
#define M 10007

int main()
{
    ll x;
    cin>>x;
    ll cnt=0;
    ll y=0;
    for(int i=1;;i++)
    {
        cnt++;
        y+=x;
        if(y%360==0)
            break;
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 3592
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() {
    ll n;
    ll t[1001],a[1001];
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> t[i]>>a[i];
    }
    ll result = 1;
    for (int i = 0; i < n-1; i++) {
        result = max((t[i]-1)/t[i+1]+1, (a[i]-1)/a[i+1]+1);
        t[i+1]*=result;
        a[i+1]*=result;
    }
    std::cout << t[n-1]+a[n-1] << std::endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N,H,W;
int main(){
	cin >> N;
	cin >> H;
	cin >> W;
	printf("%d\n",(N-H+1)*(N-W+1));
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
 
using namespace std;
 
int dfs(const vector<vector<pair<int, int> > > &v, int idx, vector<int> &used, int needs) {
    int ans = 0;
 
    for(int i = idx; i < v.size(); ++i) {
        int used_cnt = 0;
        for(int j = 0; j < v[i].size(); ++j) {
            if(used[v[i][j].first]) {
                ++used_cnt;
            }
        }
        if(used_cnt != needs) continue;
 
        used[i] = 1;
        int score = 0;
        for(int k = 0; k < used.size(); ++k) {
            if(!used[k]) continue;
            int sat = 10000000;
            for(int l = 0; l < v[k].size(); ++l) {
                if(used[v[k][l].first]) sat = min(sat, v[k][l].second);
            }
            if(sat == 10000000) sat = 0;
            score += sat;
            //cout << k << ' ';
        }
        //cout << ':' << score << endl;
        ans = max(ans, score);
        ans = max(ans, dfs(v, i+1, used, needs+1));
        used[i] = 0;
    }
 
    return ans;
}
 
int main() {
    int N, M;
    cin >> N >> M;
 
    vector<vector<pair<int, int> > > friends(N);
    for(int i = 0; i < M; ++i) {
        int u, v, f;
        cin >> u >> v >> f;
        --u; --v;
        friends[u].push_back(make_pair(v, f));
        friends[v].push_back(make_pair(u, f));
    }
 
    vector<int> tmp(N, 0);
    cout << dfs(friends, 0, tmp, 0) << endl;
 
    return 0;
}

Measured memory_bytes: 3112
# include <bits/stdc++.h>
# define rep(i, n) for (ll i = 0; i < (n); i++)
# define reps(i, n) for (ll i = 1; i <= (n); i++)
# define foreps(i, m, n) for (ll i = (m); i < (n); i++)
# define len(x) ((int)(x).size())
# define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
const long long mod = 1e9 + 7;
const long long inf = 1e18;

int main() {
    ll N, M; cin >> N >> M;
    vector<bool> A(200050, false), B(200050, false);
    rep(i, M) {
        ll a, b; cin >> a >> b;
        if (a == 1) A[b] = true;
        if (b == N) B[a] = true;
    }

    rep(i, 200050) {
        if (A[i] && B[i]) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 3680
#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define LOCAL 1

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define dbg(...) cout<<#__VA_ARGS__ ": ["; for(auto e: __VA_ARGS__){cout<<e<<", ";} cout<<"]\n"
#define dbg1(...) cout<<#__VA_ARGS__ " "<< __VA_ARGS__ 
#else
#define dbg(...) 1;
#define dbg1(...) 1;
#endif

typedef long long ll;
typedef unsigned long long ull;
constexpr int R=5e6+69, INF=2e9+6969;

int qq;

int main()
{
	int a,b,c,k;
	cin >> a >> b >> c >> k;
	while(k>0 && a>=b) 
	{
		--k;
		b<<=1;
	}
	while(k>0 && b>=c) 
	{
		--k;
		c<<=1;
	}
	if(c>b && b>a) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>
int main(){
  int a,b,i;
  scanf("%d%d",&a,&b);
  for(i=1; i<=20; i++){
    if(b==1){
      printf("0\n");
      break;
    }
    if(a+(a-1)*(i-1)>=b){
      printf("%d\n",i);
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
int main(){
    string s;
    cin >> s;
    int q;
    cin >> q;
    int rev = 0;
    rep(i,q){
        int t;
        cin >> t;
        if(t == 1)rev++;
        else{
            int f;
            char c;
            cin >> f >> c;
            if((f+rev)%2 == 1)s.insert(s.begin(),c);
            else s.push_back(c);
        }
    }
    if(rev%2 == 1)reverse(all(s));
    rep(i,s.size())cout << s[i];
    cout << endl;
}

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

using namespace std;

int main() {
	int n;

	cin >> n;

	vector<int> b(n);
	vector<int> f(n);
	vector<int> r(n);
	vector<int> v(n);
	int bin;
	int fin;
	int rin;
	int vin;

	for (int i = 0; i < n; i++) {
		cin >> bin >> fin >> rin >> vin;
		b[i] = bin;
		f[i] = fin;
		r[i] = rin;
		v[i] = vin;
	}

	int ans[10][15] = { 0 };
	for (int j = 0;j < n;++j) {
		ans[r[j] - 1][4 * (b[j] - 1) + f[j] - 1] += v[j];
	}

	for (int n = 0;n < 15;++n) {
		if (n % 4 == 3) {
			cout << "####################";
		}
		else {
			for (int m = 0; m < 10;++m) {
				cout << " " << ans[m][n];
			}
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3108
#include <cstdio>
int n, d, x;
int main() {
	scanf("%d%d%d", &n, &d, &x);
	double first = d, p = x;
	double ans = 0;
	for(int len = 2 * n; len > 0; len -= 2) {
		ans += (2 * first + (len - 1) * p) / 2;
		first = ((len + 2) * first + 5 * p) / len;
		p = (len + 4) * p / len;
	}
	printf("%f\n", ans);
	return 0;
}


Measured memory_bytes: 128
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 100000000


s, c = LI()
if c <= s * 2:
    print(c // 2)
else:
    print((c - s * 2) // 4 + s)

Measured memory_bytes: 39792
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int n, m; ll x;
    cin >> n >> m >> x;
    vector<ll> c(n);
    vector<vector<ll>> a(n);
    rep(i, n) {
        cin >> c[i];
        rep(j, m) {
            ll t; cin >> t;
            a[i].push_back(t);
        }
    }

    ll ans = LLINF;
    for (int bits = 0; bits < (1 << n); bits++) {
        vector<ll> rikaido(m, 0);
        rep(i, n) {
            if (bits & (1 << i)) {
                rep(j, m) {
                    rikaido[j] += a[i][j];
                }
            }
        }

        bool ok = true;
        rep(j, m) {
            if (rikaido[j] < x) ok = false;
        }

        if (ok) {
            ll sum = 0;
            rep(i, n) {
                if (bits & (1 << i)) sum += c[i];
            }
            chmin(ans, sum);
        }
    }
    if (ans == LLINF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define int long long int
using namespace std;
template<typename T,typename U> using P=pair<T,U>;
template<typename T> using V=vector<T>;
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}

template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}
#define DUMP(x)  cerr<<#x<<" = "<<(x)<<endl;

struct edge { int to, cost; };

const int INF = 1e18;
const int MOD = 1e9+7;

signed main()
{
   int n; cin >> n;
   V<double> p(n);
   for (int i = 0; i < n; i++) {
      cin >> p[i];
   }

   V<V<double>> dp(n+1, V<double>(n+1));
   dp[0][0] = 1;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j <= i; j++) {
         dp[i+1][j+1] += dp[i][j] * p[i];
         dp[i+1][j] += dp[i][j] * (1 - p[i]);
      }
   }
   double sum = accumulate(dp[n].begin()+n/2+1, dp[n].end(), 0.);
   printf("%.9lf\n", sum);

   return 0;
}


Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
int main() {
  int64_t n,i,j,m=0;
  cin>>n;
  vector<vector<int64_t>> a(n,vector<int64_t>(2));
  vector<vector<int64_t>> dp(n+1,vector<int64_t>(n+1));
  for(i=0;i<n;i++) {
    cin>>a.at(i).at(0);
    a.at(i).at(1)=i+1;
  }
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  for(i=0;i<=n;i++) {
    for(j=0;j<=i;j++) {
      if (i==0) dp.at(j).at(i-j)=0;
      else if (i==j) dp.at(j).at(i-j)=dp.at(j-1).at(i-j)+a.at(i-1).at(0)*(a.at(i-1).at(1)-i);
      else if (j==0) dp.at(j).at(i-j)=dp.at(j).at(i-j-1)+a.at(i-1).at(0)*(n+1-i-a.at(i-1).at(1));
      else dp.at(j).at(i-j)=max(dp.at(j-1).at(i-j)+a.at(i-1).at(0)*(a.at(i-1).at(1)-j),dp.at(j).at(i-j-1)+a.at(i-1).at(0)*(n+1-i+j-a.at(i-1).at(1)));
    }
  }
  for(i=0;i<=n;i++) if (m<dp.at(i).at(n-i)) m=dp.at(i).at(n-i);
  cout<<m<<endl;
}

Measured memory_bytes: 34664
#include <stdio.h>
int main(void)
{	
	int N,i,a,b,c;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d%d%d",&a,&b,&c);
		if(a>b && a>c)
			puts( a*a == b*b + c*c ? "YES" : "NO");
		else if(b>a && b>c)
			puts( b*b == a*a + c*c ? "YES" : "NO");
		else
			puts( c*c == a*a + b*b ? "YES" : "NO");
	}
	return 0;
}

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

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

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

const ll MOD = 998244353;
ll mpow(ll a, ll n) // a^n
{
	if (n == 0) return 1;
	ll res = mpow(a, n / 2);
	res = res * res % MOD;
	if (n % 2) res = res * a % MOD;
	return res;
}

ll frac[200001];
ll ncr(ll n, ll r)
{
	ll res = frac[n];
	res *= mpow(frac[r], MOD - 2);
	res %= MOD;
	res *= mpow(frac[n - r], MOD - 2);
	res %= MOD;

	return res;
}

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

	frac[0] = 1;
	for (ll i = 1; i <= 200000; i++)
	{
		frac[i] = frac[i - 1] * i % MOD;
	}
	
	ll n, m, k; cin >> n >> m >> k;

	ll ans = 0;
	for (ll i = n; i >= n - k; i--)
	{
		ll res = m;
		res *= mpow(m - 1, i - 1);
		res %= MOD;

		res *= ncr(n - 1, i - 1);
		res %= MOD;

		ans += res;
		ans %= MOD;
	}

	cout << ans;
}

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

Measured memory_bytes: 1156
#include <iostream>

int main(int argc, const char * argv[]) {
    int a = 0;
    int b = 0;
    int ab = 0;
    int o = 0;
    int k;
    char s[5];
    
    while (scanf("%d,%s",&k,s)!= EOF){
        if(s[0] == 'A' && s[1] == 'B'){
            ab = ab + 1;
        }else if(s[0] == 'A'){
            a++;
        }else if(s[0] == 'B'){
            b++;
        }else if(s[0] == 'O'){
            o++;
        }
        

        
    }         std::cout << a << std::endl;
        std::cout << b << std::endl;
        std::cout << ab << std::endl;
        std::cout << o << std::endl;
    
        }

Measured memory_bytes: 3224
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

#define LL long long

const int maxn = 100005;
int a[maxn];

int main()
{
    int n;
    int x;
    while(scanf("%d%d", &n, &x)==2)
    {
        LL sum = 0;
        for(int i = 0; i < n; i++ )
            scanf("%d", &a[i]);
        if(a[0]>x)
        {
            sum += a[0]-x;
            a[0] = x;
        }
        for(int i = 1; i < n; i++ )
        {
            if(a[i]+a[i-1]>x)
            {
                sum += a[i]+a[i-1]-x;
                a[i] = abs(a[i]+a[i-1]-x-a[i]);
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);i++)
int main(){
    string s;
    string s1="",s2="";
    cin >> s;
    int q;
    cin >> q;
    bool f = 1;
    while(q--)
    {
        int que;
        cin >> que;
        if (que == 1)
        {
            f ^= 1;
        }else
        {
            int a;
            char c;
            cin >> a >> c;
            if((f==1&&a==1)||(f==0&&a==2))
            {
                s1 += c;
            }else
            {
                s2 += c;
            }
        }
    }
    if(f==1){
        reverse(s1.begin(),s1.end());
        cout << s1 << s << s2 << endl;
    }else
    {
        reverse(s.begin(),s.end());
        reverse(s2.begin(),s2.end());
        cout << s2 << s << s1 << endl;
    }
}


Measured memory_bytes: 1088
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

acum1 = [0]
for i in range(n):
    acum1.append(acum1[-1]+a[i])

acum2 = [0]
for i in range(m):
    acum2.append(acum2[-1]+b[i])
ans = 0
j = m
for i in range(n+1):
    if acum1[i]>k:
        break
    while acum2[j]>k-acum1[i] and j>0:
        j -= 1
    ans = max(ans,i+j)
print(ans)
        

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

int main(){
	string a,b,c;cin>>a>>b>>c;
  	string ret="";
  	ret.push_back(a[0]-('a'-'A'));
  	ret.push_back(b[0]-('a'-'A'));
  	ret.push_back(c[0]-('a'-'A'));
  	cout<<ret<<endl;

}

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

int main(){
    long long int t1, t2, a1, a2, b1, b2;
    cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;

    if(t1 * a1 + t2 * a2 == t1 * b1 + t2 * b2){
        cout << "infinity" << endl;
        return 0;
    }

    if(t1 * a1 + t2 * a2 < t1 * b1 + t2 * b2){
        swap(a1, b1);
        swap(a2, b2);
    }

    if(a1 > b1){
        cout << 0 << endl;
        return 0;
    }

    long long int dist1 = (b1 - a1) * t1;// > 0
    long long int dist2 = (t1 * a1 + t2 * a2) - (t1 * b1 + t2 * b2);// > 0

    long long int k = dist1 / dist2;
    long long int ans = k + (k - max(0LL, (dist1 - (a2 - b2) * t2) / dist2)) + 1;
    if(dist1 % dist2 == 0) ans -= 1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const ll INF = 1e15;
const ll MOD = 1e9 + 7;

int main(){
	int n5 = 0;
	int n7 = 0;
	for (int i = 0; i < 3; i++){
		int a;
		cin >> a;
		if (a == 5){
			n5++;
		}
		if (a == 7){
			n7++;
		}
	}
	if (n5 == 2 && n7 == 1){
		cout << "YES" << endl;
	}
	else{
		cout << "NO" << endl;
	}
	return 0;
}


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

//Pollock's conjecture
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] p = new int[181];
		for(int i=1;i<181;i++){
			p[i] = (i*(i+1)*(i+2))/6;
		}
		int[] dp = new int[1000000+1];
		int[] dp2 = new int[1000000+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		Arrays.fill(dp2, Integer.MAX_VALUE);
		dp[0] = 0;
		dp2[0] = 0;
		for(int i=1;i<=1000000;i++){
			for(int j=1;j<181;j++){
				if(i-p[j]>=0){
					dp[i] = Math.min(dp[i], dp[i-p[j]]+1);
					if(p[j]%2==1){
						dp2[i] = Math.min(dp2[i], dp2[i-p[j]]+1);
					}
				}
			}
		}
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			System.out.println(dp[n]+" "+dp2[n]);
		}
	}
}

Measured memory_bytes: 0
#include <stdio.h>
#define LL long long
#define maxn 100010
LL sum,a[maxn],cnt[maxn];
int main(){
	int i,n,q,b,c;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]),sum+=a[i],cnt[a[i]]++;
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&b,&c);
		sum-=cnt[b]*b;
		sum+=cnt[b]*c;
		cnt[c]+=cnt[b],cnt[b]=0;
		printf("%lld\n",sum);
	}
	return 0;
}

Measured memory_bytes: 3292
import sys
sys.setrecursionlimit(2 * 10 ** 5)

N, K = map(int, sys.stdin.readline().strip().split())
A = list(map(int, sys.stdin.readline().strip().split()))

town_line = []
town_set = set()
last_town = None


def search(town=0):
    global last_town
    if town not in town_set:
        town_line.append(town)
        town_set.add(town)
        search(town=A[town]-1)
    else:
        last_town = town
        return


search(0)
town_loop = town_line[town_line.index(last_town):]

if K < len(town_line):
    print(town_line[K] + 1)
else:
    k = K - len(town_line) + 1
    k = k % len(town_loop)
    print(town_loop[k - 1] + 1)


Measured memory_bytes: 238492
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define cool ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
int main()
{ 
    cool;
    int a,b,c,d,f=1,ans;
    cin>>a>>b>>c>>d;
    while(1){
    	if(a<=0){
    		ans=1;
    		break;
		}
		else if(c<=0){
			ans=2;
			break;
		}
    	if(f==1){
    		c-=b;
    		f=2;
		}
		else if(f==2){
			a-=d;
			f=1;
		}
	}
	if(ans==2)
		cout<<"Yes";
	else
	cout<<"No";
    return 0;
}


Measured memory_bytes: 3640
//start of jonathanirvings' template v3.0.3 (BETA)

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
}

//end of jonathanirvings' template v3.0.3 (BETA)

int n;
int data[100005];

int main()
{
  scanf("%d",&n);
  REPN(i,n) scanf("%d",&data[i]);
  int risan = 0;
  REPN(i,n) if(data[data[i]] == i) ++risan;
  printf("%d\n",risan/2);
  return 0;
}










Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;

int syc(long i,long Min,long Max){
	if(Min <= i && i <= Max){
		return 1;
	}else{
		exit(1);
		//return 0;
	}
}

int main(){
	
	int a,b;
	
	cin  >> a;
	syc(a,1,100);
	
	cin  >> b;
	syc(b,0,100);
	
	for(int i=0;i<2*a-1;i++){
		cout << b-(a-1)+i << " ";	
	}
	
	cout << endl;
	
	return 0;	
}


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

using namespace std;
typedef long long ll;
typedef double ld;

ll n, k;
ll a[1010];
ll sum;

int main(void)
{
	scanf("%lld %lld", &n, &k);
	
	for(ll i = 0 ; i < n ; i++)
		scanf("%lld", &a[i]);
	
	sort(a, a + n);
	
	for(ll i = 0 ; i < k ; i++)
		sum += a[i];
	
	printf("%lld", sum);
	return 0;
}

Measured memory_bytes: 3764
#include<bits/stdc++.h>
using namespace std;
#define INS(x) x.begin(),x.end()
#define debug(x) cout<<x;
    

    
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long n,k;
    cin>>n>>k;

    if (n%k==n) cout<<min(n,k-n)<<'\n';
    else if (n%k==0) cout<<0<<'\n';
    else cout<<min(k-n%k,n%k)<<'\n';
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<map>
#include<random>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include <queue>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney, tree, chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun

#define REP(i,a,b) for(ll i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIY PRI("Yes")
#define PRIN PRI("No")



int main() {
	ll N, M;
	cin >> N >> M;
	vector<vector<ll>> dp(M + 1);
	ll inf = (ll)1e18;
	REP(i, 0, M + 1)dp[i].resize(4096, inf);
	dp[0][0] = 0;
	REP(i, 1, M + 1) {
		ll a, b, f = 0;
		cin >> a >> b;
		REP(j, 0, b) {
			ll c;
			cin >> c;
			f |= (1 << (c - 1));
		}
		REP(j, 0, 4096) {
			dp[i][j] = dp[i - 1][j];
			ll xx = ~(f);
			ll x = j & (xx);
			ll y = dp[i - 1][x];
			dp[i][j] = min(dp[i][j], min(dp[i - 1][j], y+a));
		}
	}
	ll f = 0;
	REP(i, 0, N) f |= (1 << i);
	if (dp[M][f] >= inf) PRI(-1);
	else PRI(dp[M][f]);
	return 0;
}




Measured memory_bytes: 35604
main = do
  s <- getContents
  let v = map (map read . words) . lines $ s
  let w = map solve v
  let x = map (\x-> if x then "YES" else "NO") $ w
  mapM_ putStrLn x

solve::[Double] -> Bool
solve [xa,ya,xb,yb,xc,yc,xd,yd] =
  abs(dot u v) < eps
  where u = (xb-xa, yb-ya)
        v = (xd-xc, yd-yc)
        dot (a,b) (c,d) = a*c + b*d
        eps=1e-10

Measured memory_bytes: 4400
#include <iostream>
#include <string>
#include <list>
using namespace std;

int main()
{
  int N,L;
  cin >>N>>L;
  list<string> list;
  for (int i = 0; i < N; i++) {
    string str;
    cin>>str;
    list.push_back(str);
  }
  list.sort();
  for(string a:list){
    cout<<a;
  }
  cout<<endl;
  return 0;
}

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

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N, L;
		N = scanner.nextInt();
		L = scanner.nextInt();
		String[] S = new String[N];
		for (int i = 0; i < S.length; i++) {
			S[i] = scanner.next();
		}
		Arrays.sort(S);
		for (int i = 0; i < S.length; i++) {
			System.out.print(S[i]);
			;

		}
		System.out.println("");
	}
}

Measured memory_bytes: 10064
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

#define MAX(a, b) ((a) < (b) ? (b) : (a))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

using namespace std;
int main()
{
  int n, c_;
  cin >> n >> c_;
  int s[n], t[n], c[n];
  const int TMAX = 100000 + 1;

  int tmp[c_][TMAX];
  for (int i = 0; i < c_; i++)
    for (int j = 0; j < TMAX; j++)
      tmp[i][j] = 0;

  for (int i = 0; i < n; i++)
  {
    cin >> s[i] >> t[i] >> c[i];
    c[i]--;
    tmp[c[i]][s[i]]++;
    tmp[c[i]][t[i]]--;
  }

  int a[TMAX * 2 + 2];
  for (int i = 0; i < TMAX * 2 + 2; i++)
  {
    a[i] = 0;
  }

  for (int i = 0; i < c_; i++)
  {
    for (int j = 0; j < TMAX; j++)
    {
      if (tmp[i][j] == 1)
      {
        a[j * 2 - 1]++;
      }
      else if (tmp[i][j] == -1)
      {
        a[j * 2]--;
      }
    }
  }
  int ans = 0;
  for (int i = 0, s = 0; i < TMAX * 2 + 2; i++)
  {
    s += a[i];
    ans = MAX(ans, s);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 13952
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define maxn 1000005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    double n;
    cin >> n;
    cout << fixed << setprecision(10) << n * 2 * acos(-1) << '\n';
}


Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    long long mod=1e9+7;
    cin>>n>>m;
    vector<bool> hole(n+1,0);
    for(int i=0;i<m;i++){
        int a;
        cin>>a;
        hole[a]=true;
    }
    vector<long long int> count(n+1,0);
    count[0]=1;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<=min(n,i+2);j++){
            if(hole[j])continue;
            count[j]+=count[i];
            count[j]%=mod;
        }
    }
    cout<<count[n]<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
float PHI = 1.6180339;
const float  PI_F=3.14159265358979f;
#define MAX 1000 m
#define endl "\n"    
#define manhunt 32 
//typedef long long float;
#define int long long
typedef pair<int, int> pii;
//#define float unsigned long long
typedef pair<int, int> pii;
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define CHAR_SIZE 26 
#define pi pair<int,int> 

int modpow(int x, int n, int m) { if (n == 0) return 1%m; long long u = modpow(x,n/2,m); u = (u*u)%m; if (n%2 == 1) u = (u*x)%m; return u; } 


int add(int x, int y) 
{
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
int sub(int x, int y) 
{
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
int inv(int a, int m = MOD)
{
	return modpow(a, m - 2, m);
}
int mul(int a, int b) 
{
	return (long long) a * b % MOD2;
}


int nCrModp(int n, int r, int p) 
{ 
    int C[r+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1; 
    for (int i = 1; i <= n; i++) 
    { 
        for (int j = min(i, r); j > 0; j--) 
            C[j] = (C[j] + C[j-1])%p; 
    } 
    return C[r]; 
} 

int isPalindrome(string a)
{
    string rev=a;
    reverse(a.begin(),a.end());
    if(a==rev)
    return 1;
    else
    return 0;
}


int32_t main()
{
    FAST
    cout << fixed << setprecision(12);
 
    int n;
    cin>>n;
    int arr[n+10];
    int freq[n+10];
    for(int i=0;i<=n;i++)
    {
        freq[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        ++freq[arr[i]];
    }

    vector<int>v;
    for(int i=0;i<=n;i++)
    {
        if(freq[i]>0)
        {
            v.push_back(freq[i]);
        }
    }
    int tot=0;
    for(int i=0;i<v.size();i++)
    {
        int x=v[i];
        int y=(x*(x-1))/2;
        tot+=y;
    }
    for(int i=0;i<n;i++)
    {
        int dp=tot;
        int x=freq[arr[i]];
        int y=(x*(x-1))/2;
        int z=((x-1)*(x-2))/2;
        dp-=y;
        dp+=z;
        cout<<dp<<endl;
    }



    return 0;
}


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

#define FOR(i, a, b) for(int i = a; i<b; ++i)
#define FR(a, b) for(int i = a; i>=b;--i)
#define _upgrade cin.tie(0); ios_base::sync_with_stdio(0)
#define pb push_back
#define mp make_pair
#define INF 1e9+2137
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair<int, int> iPair;

const int MAX = 3e3+1;
const int M = 1e9+7;

string s, z;
void LCS()
{
    int n = s.size(), m = z.size(), dp[n+1][m+1];
    FOR(i, 0, n+1)
        dp[i][0] = 0;
    FOR(i, 0, m+1)
        dp[0][i] = 0;
    FOR(i, 1, n+1)
        FOR(j, 1, m+1)
        {
            if(s[i-1] == z[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }

    string ans = "";
    int i = n, j = m;
    while(i >= 1 && j >= 1)
    {
        if(s[i-1] == z[j-1])
        {
            ans += s[i-1];
            i--;
            j--;
        }
        else if(dp[i-1][j] >= dp[i][j-1])
            i--;
        else
            j--;
    }
    reverse(all(ans));
    cout<<ans;
}
int main()
{
    _upgrade;
    cin>>s>>z;
    LCS();
}


Measured memory_bytes: 35584
N,M,C = map(int,input().split())
blist = list(map(int,input().split()))

cnt = 0
for i in range(N):
  alist = list(map(int,input().split()))
  prod = C
  for j in range(M):
    prod += alist[j]*blist[j]
    
  if prod > 0:
    cnt += 1
    
print(cnt)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(17) << res << endl;
 
int main() {
    string s;
    cin >> s;
    auto res = 0;
    for (auto c : s) {
        if (c == '+') {
            ++res;
        } else {
            --res;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
n = int(input())
d = {'AC': 0, 'WA': 0, 'TLE': 0, 'RE': 0}

for i in range(n):
    a = input()
    d[a] += 1

print('AC x', d['AC'])
print('WA x', d['WA'])
print('TLE x', d['TLE'])
print('RE x', d['RE'])

Measured memory_bytes: 9200
using System;

namespace ABC127
{
	class Program
	{
		static void Main(string[] args)
		{
			// 入力
			int N, M;
			int[] firstArray = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
			N = firstArray[0];
			M = firstArray[1];
			int[] L = new int[M];
			int[] R = new int[M];
			for (int i = 0; i < M; i++)
			{
				int[] array = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
				L[i] = array[0];
				R[i] = array[1];
			}
			// 処理・出力
			// 全部通る番号pは(L[0]~L[M-1]の最大値)<=p<=(R[0]~R[M-1]の最小値)を満たす
			int maxL = 0;
			int minR = N;
			for (int i = 0; i < M; i++)
			{
				if (maxL < L[i])
				{
					maxL = L[i];
				}
				if (minR > R[i])
				{
					minR = R[i];
				}
			}
			// 個数計算
			int count = minR - maxL + 1;
			if (count < 0)
			{
				// 負の数になることはない
				count = 0;
			}
			Console.WriteLine(count);
		}
	}
}

Measured memory_bytes: 15812
#include<iostream>
#define MAXN 100000
using namespace std;
typedef long long ll;

int N;
int a[MAXN];
int ans;
int leftn[MAXN], rightn[MAXN];

int gcd(int a, int b) {
	if (b == 0) return a;

	return gcd(b, a%b);
}

int main() {
	ans = 1;

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

	leftn[0] = a[0];
	rightn[N - 1] = a[N - 1];
	for (int i = 1; i < N; i++) {
		leftn[i] = gcd(leftn[i-1], a[i]);
		rightn[N - 1 - i] = gcd(rightn[N - i], a[N - 1 - i]);
	}

	for (int i = 0; i < N; i++) {
		if (i == 0) {
			if (rightn[i+1] > ans) ans = rightn[i+1];
		}
		else if (i == N - 1) {
			if (leftn[i-1] > ans) ans = leftn[i-1];
		}
		else {
			int tmp = gcd(leftn[i - 1], rightn[i + 1]);
			if (tmp > ans) ans = tmp;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1408
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
//////////////

void solve() {
	int N;
	cin >> N;
	vector<LL> A(N), B(N);
	LL Bmin = INF;
	LL sum = 0;
	for(int i=0;i<N;++i){
		cin >> A[i] >> B[i];
		sum += A[i];
		if (A[i] > B[i]) {
			if (Bmin > B[i]) {
				Bmin = B[i];
			}
		}
	}
	if (Bmin == INF) {
		cout << 0 << endl;
	}
	else {
		cout << sum - Bmin << endl;
	}
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tp;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
typedef pair<pii, int> piipi;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;
typedef pair<LL, pii> plpii;
typedef pair<LD, LD> pdd;
typedef pair<LD, int> pdi;
typedef pair<LD, LL> pdl;
typedef pair<int, LD> pid;
typedef pair<LL, LD> pld;
const int mod = 1e9 + 7;
const int hf = 999983;
const int N = 1e6;

bool vis[2][3005][3005];
LL dp[2][3005][3005];
int a[3005], n;

LL dfs(int t, int s, int e){
    if(e-s+1 == 0) return 0;
    if(vis[t][s][e]) return dp[t][s][e];
    vis[t][s][e] = 1;
    if(t == 0) return dp[t][s][e] = max(dfs(1-t, s+1, e) + a[s], dfs(1-t, s, e-1) + a[e]);
    else return dp[t][s][e] = min(dfs(1-t, s+1, e) - a[s], dfs(1-t, s, e-1) - a[e]);
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    printf("%lld\n", dfs(0, 1, n));
}


Measured memory_bytes: 159232
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s[100],sa;
	int i,a,l,n;
	cin>>n>>l;
	for(i=0;i<n;i++)
		cin>>s[i];
	for(i=1;i<=n-1;i++)
	{
		for(a=n-1;a>=i;a--)
		{
			if(s[a]<s[a-1])
				swap(s[a],s[a-1]);
		}
	}
	for(i=0;i<n;i++)
		sa=sa+s[i];
	cout<<sa;
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t;cin >> s >>t;
  int ans = 0;
  for(int i = 0; i < s.size(); i++){
    if(s.at(i) != t.at(i)) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3908
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <cctype>
#include <cstring>
#define rep(i, m, n) for (int i = m; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define ll long long
#define ull unsigned long long
#define push(a) push_back(a)
#define pop(a) pop_back(a)
#define debug(x) cout << #x << ": " << x << endl
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

ull n,k,cnt=0,cnt1=0,ans=0;
ull a,num[200005]={};
string s;

int main(){
    cin>>n>>k;
    for(ull i=0; i<n; i++){
       cin>>a;
       num[a-1]++;
    }
    for(int i=0; i<200000; i++){
        if(num[i]>0)cnt++;
    }
    
    sort(num,num+n);
    
    for(ull i=0; i<n; i++){
        if((cnt1==cnt-k) || (cnt < k))break;
        if(num[i]>0){
            ans+=num[i];
            cnt1++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){long n,d,x=0;cin>>n>>d;
         for(long i=0;i<n;i++){long s,t;cin>>s>>t;
                        if(s*s+t*t-d*d<=0)x++;}
           cout<<x<<endl;}

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    int ans = 0;
    rep2(i,1,n-1) {
        int a = p[i-1],b = p[i],c = p[i+1];
        int u = max(a,max(b,c));
        int d = min(a,min(b,c));
        if(b != u && b != d) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256