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

using namespace std;

#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()

const int MX = (int)1e5 + 10;
const int mod = (int)1e9 + 7;

void add_self(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub_self(int &x, int y){x -= y; if(x < 0) x += mod;}
void mul(int &x, int y){x = x * 1LL * y % mod;}


int main(){

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    int x[m], y[m], c[m];

    vector<int> st[n], nd[n];

    for(int i = 0; i < m; ++i){
        cin >> x[i] >> y[i] >> c[i];
        --x[i], --y[i];
        st[x[i]].push_back(i);
        nd[y[i]].push_back(i);
    }

    ll best[n];
    memset(best, 0x7f, sizeof best);
    best[0] = 0;

    multiset<ll> ms;

    for(int i = 0; i < n; ++i){

        if (not ms.empty())
            best[i] = min(best[i], *ms.begin());

        for(auto &idx : st[i]){
            ms.insert(best[i] + c[idx]);
        }
        
        for(auto &idx : nd[i]){
            auto it = ms.find(best[x[idx]] + c[idx]);
            assert(it != ms.end());
            ms.erase(it);
        }
    }

    ll res = best[n - 1];
    if(res >= n * 1LL * 1e9) res = -1; 

    cout << res << endl;

    return 0;
}

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

using namespace std;

using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FORE(i, a, b) for(int i=(a);i<=(b);++i)
#define FORR(i, a, b) for(int i=(b-1);i>=(a);--i)
#define FORRE(i, a, b) for(int i=(b);i>=(a);--i)
#define rep(i, n) for(int i=0;i<(n);++i)
#define repe(i, n) for(int i=0;i<=(n);++i)
#define repr(i, n) for(int i=(n-1);i>=0;--i)
#define repre(i, n) for(int i=(n);i>=0;--i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)
typedef pair<int, int> P;
const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

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

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int a,b,c;
	cin>>a>>b>>c;
	
	cout<<min(b/a, c)<<endl;
	
	return 0;
}

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

int main(){
    int A, B, K;
    cin >> A >> B >> K;

    for (int i = 0; i < K; ++i){
        if (i % 2 == 0){
            if (A % 2 == 1) --A;
            B += A / 2;
            A /= 2;
        } else{
            if (B % 2 == 1) --B;
            A += B / 2;
            B /= 2;
        }
    }

    cout << A << " " << B << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;

int main() {
/*    scanf("%lld", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &A[i]);
        if (A[i] <= 100) cnt[A[i]]++;
    }

    long long Answer = 0;
    for (int i = 1; i <= 50; i++) Answer += cnt[i] * cnt[101 - i];
    cout << Answer << endl;
*/
    int K, A, B, b= 0;
    scanf("%d", &K);
    scanf("%d %d", &A, &B);
    for(int i = A; i <= B ; i++ ){
        if (i % K == 0) { b = 1; break; }
    }
    if(b == 1){ printf("OK\n"); }
    else printf("NG\n");

    return 0;
}

Measured memory_bytes: 3664
def get_char_value(char):
    if char == "C":
        return 1;
    if char == "A":
        return 2;
    if char == "G":
        return 3;
    if char == "T":
        return 4;

def get_string_value(string):
    s = 0;
    p = 1;
    for char in string:
        s += p * get_char_value(char);
        p *= 5;
    return s;

def h1(value, M):
    return value % M;

def h2(value, M):
    return 1 + value % (M - 1);

def insert(dic, M, string):
    value = get_string_value(string);
    h1_value = h1(value, M);
    h2_value = h2(value, M);
    i = 0;
    while True:
        index = (h1_value + i * h2_value) % M;
        if dic[index] == string:
            break;
        elif dic[index] is None:
            dic[index] = string;
            break;
        i += 1;

def find(dic, M, string):
    value = get_string_value(string);
    h1_value = h1(value, M);
    h2_value = h2(value, M);
    i = 0;
    while True:
        index = (h1_value + i * h2_value) % M;
        if dic[index] == string:
            return True;
        elif dic[index] is None:
            return False;
        i += 1;

M = 1046527;
dic = [None for i in range(M)];
count = int(input());
for i in range(count):
    command = input().split();
    if command[0] == "insert":
        insert(dic, M, command[1]);
    elif command[0] == "find":
        if find(dic, M, command[1]):
            print("yes");
        else:
            print("no");




Measured memory_bytes: 31056
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  V<> a(n), b(n);
  for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
  V<> c(m), d(m);
  for (int j = 0; j < m; ++j) cin >> c[j] >> d[j];
  for (int i = 0; i < n; ++i) {
    int mn = 1e9, mj = -1;
    for (int j = 0; j < m; ++j) {
      int crr = abs(a[i] - c[j]) + abs(b[i] - d[j]);
      if (crr < mn) {
        mn = crr;
        mj = j;
      }
    }
    cout << mj + 1 << '\n';
  }
}

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

struct UnionFind {
  vector<int> d;
  UnionFind(int n): d(n,-1) {}
  int root(int x) {
    if (d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return root(x) == root(y);}
  int size(int x) { return -d[root(x)];}
};

int deg[100005];
vector<int> to[100005];

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  UnionFind uf(n);
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    deg[a]++;
    deg[b]++;
    uf.unite(a,b);
  }
  rep(i,k) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  rep(i,n) {
    int ans = uf.size(i)-1-deg[i];
    for (int u : to[i]) {
      if (uf.same(i,u)) --ans;
    }
    printf("%d%c", ans, i==n-1?'\n':' ');
  }
  return 0;
}


Measured memory_bytes: 7040
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;

using namespace std;

int main(void){
    int N, sum=0,count=0, d[100];
    cin>>N;
    rep(i, N){
        cin >> d[i];
        sum+=d[i];
    }
    rep(i, N){
        count+=(sum-d[i])*d[i];
    }
    cout <<count/2 <<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int x[1010],y[1010];
double MIN(double a,double b){return a<b?a:b;}
double MAX(double a,double b){return a>b?a:b;}
double px,py;
int f(int i,int j,int k){
  double a=2*(x[i]-x[j]),b=2*(y[i]-y[j]),c=2*(x[i]-x[k]),d=2*(y[i]-y[k]);
  double e=x[i]*x[i]-x[j]*x[j]+y[i]*y[i]-y[j]*y[j];
  double f=x[i]*x[i]-x[k]*x[k]+y[i]*y[i]-y[k]*y[k];
  double n=a*d-b*c;
  if(fabs(n)<1e-9)return 1;
  //printf("n!!%lf\n",n);
  px=(e*d-b*f)/n;
  py=(a*f-e*c)/n;
  return 0;
}
//long long g(long long x,long long y){return x*x+y*y;}
int main(){
  int n,i,j,k,l;
  double  min=1e18,d,e,max;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d %d",&x[i],&y[i]);
  if(n==2){
    printf("%.10lf\n",hypot(x[0]-x[1],y[0]-y[1])/2.0);
    return 0;
  }
  for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
      px=(x[i]+x[j])/2.0;
      py=(y[i]+y[j])/2.0;
      for(k=max=0;k<n;k++){
	max=MAX(max,hypot(x[k]-px,y[k]-py));
      }
      min=MIN(min,max);
    }
  }
  //printf("%.10lf\n",min);
  for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
      for(k=j+1;k<n;k++){
	if(f(i,j,k))continue;
	//printf("%lf %lf\n",px,py);
	d=hypot(px-x[i],py-y[i]);
	for(l=0;l<n;l++){
	  e=hypot(px-x[l],py-y[l]);
	  if(d+1e-6<e)goto NEXT;
	}
	min=MIN(min,d);
      NEXT:;
      }
    }
  }
  printf("%.10lf\n",min);
  return 0;
}
  


Measured memory_bytes: 128
def abc075_d():
    n, k = map(int, input().split())
    P = []
    xarr = []
    yarr = []
    for _ in range(n):
        x, y = (int(x) for x in input().split())
        P.append((x, y))
        xarr.append(x)
        yarr.append(y)
    xarr.sort()
    yarr.sort()

    def count_inside(xi, xj, yi, yj)->int:
        res = 0
        for x, y in P:
            if xarr[xi] <= x and x <= xarr[xj] and yarr[yi] <= y and y <= yarr[yj]:
                res += 1
        return res

    ans = 5*10**18
    for xi in range(n-1):
        for xj in range(xi+1, n):
            for yi in range(n-1):
                for yj in range(yi+1, n):
                    if count_inside(xi, xj, yi, yj) >= k:
                        area = (xarr[xj] - xarr[xi]) * (yarr[yj] - yarr[yi])
                        ans = min(ans, area)
    print(ans)

if __name__ == '__main__':
    abc075_d()

Measured memory_bytes: 74576
#[allow(unused_imports)]
use std::io::{stdin, Read, StdinLock};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BinaryHeap};
#[allow(unused_imports)]
use std::vec::Vec;

#[allow(dead_code)]
const INF: i32 = 1000_000_000;
#[allow(dead_code)]
const INFLL: i64 = 1000_000_000_000_000_000;
#[allow(dead_code)]
const EPS: f64 = 1.0e-10;
#[allow(dead_code)]
const MOD: i32 = 1000_000_007;

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

impl<'a> Scanner<'a> {
    #[allow(dead_code)]
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner {cin: cin}
    }

    #[allow(dead_code)]
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
                    .skip_while(|c| c.is_whitespace())
                    .take_while(|c| !c.is_whitespace())
                    .collect::<String>();
        token.parse::<T>().ok()
    }

    #[allow(dead_code)]
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);
    let n: usize = sc.read();
    let mut y: usize = sc.read();
    y /= 1000;
    let mut ans = (-1, -1, -1);
    'outer: for i in 0..n+1 {
        'inner: for j in 0..n+1 {
            if i + j > n {
                continue;
            }
            let k = n - i - j;
            if i + 5 * j + k * 10 == y {
                ans = (i as i32, j as i32, k as i32);
                break 'outer;
            }
        }
    }
    println!("{} {} {}", ans.2, ans.1, ans.0);
}

Measured memory_bytes: 4352
import sys
from collections import defaultdict

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

d = defaultdict(int)
for i in a:
    d[i] += 1

for i in a:
    if d[i] > 1:
        print("NO")
        exit()

print("YES")


Measured memory_bytes: 126856
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const ll oo = 1e18;
const ll mod = 1e9 + 7,maxn = 1000010;
const double PI = acos(-1);
vector<ll> fat(maxn), inv(maxn);
ll memo[30][30];

ll fexp(ll base, ll p){
    ll ans = 1;

    while (p){
        if(p&1) ans = (ans * base)%mod;
        base = (base * base)% mod;
        p = p >> 1;
    }
    return ans;
}

void init(){
    fat[0] = fat[1] = inv[1] = 1;
    for (ll i=2; i<maxn; i++){
        fat[i] = (fat[i-1] * i)%mod;
        inv[i] = fexp(fat[i], mod-2);
    }
}

ll combina(ll n, ll k){
    if (n == k || k == 0) return 1;
    if (n < k) return 0;

    return (((fat[n] * inv[k])%mod)*inv[n - k])%mod;
}

int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, aux;
    vector<vector <int>> b(3, vector<int>(3)), m(3, vector<int>(3, 0));
    set<int> mark;
    for (int i=0; i<3; i++){
        for (int j=0; j<3; j++){
            cin >> b[i][j];
        }
    }

    cin >> n;

    for (int i=0; i<n; i++){
        cin >> aux;
        mark.insert(aux);
    }

    for (int i=0; i<3; i++){
        for (int j=0; j<3; j++){
            if (mark.count(b[i][j])) m[i][j] = 1;
        }
    }
    string ans = "No";
    for (int i=0; i<3; i++){
        if (m[i][0] + m[i][1] + m[i][2] == 3) ans = "Yes";
        if (m[0][i] + m[1][i] + m[2][i] == 3) ans = "Yes";
    }
    if (m[0][0] + m[1][1] + m[2][2] == 3) ans = "Yes";
    if (m[0][2] + m[1][1] + m[2][0] == 3) ans = "Yes";

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
#define tl 1'000'000'007
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REREP(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, a, n) for (ll i = a; i < n; i++)
#define REFOR(i, n, a) for (ll i = n; i >= a; i--)
struct P{
    ll b,c;
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false); 
    ll n,m;
    cin >> n >> m;
    vector<ll>A(n);
    vector<P>T(m);
    REP(i,n) cin >> A[i];
    REP(i,m) cin >> T[i].b >> T[i].c;
    sort(A.begin(), A.end());
    sort(T.begin(), T.end(), [](const P &x, const P &y){ return x.c>y.c;});
    ll ii= 0;
    REP(i,T.size()){
        REP(j,T[i].b){
            // cout << A[ii] << " ";
            A[ii]= max(A[ii], T[i].c);
            
            ii++;
            if(ii>=n){
                break;
            }
        }
        if(ii>=n){
            break;
        }
    }
    ll sum= 0;
    REP(i,n){
        sum+= A[i];
    }
    cout << sum << endl;
}


Measured memory_bytes: 2560
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
#include <map>

using namespace std;

template<typename T>
T gcd(T a, T b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    vector<int> front(n), back(n);
    int temp = a[0];
    for(int i = 0; i < n; i++){
        temp = gcd(temp, a[i]);
        front[i] = temp;
    }
    temp = a[n-1];
    for(int i = n-1; i >= 0; i--){
        temp = gcd(temp, a[i]);
        back[i] = temp;
    }
    int ans = max(front[n-2], back[1]);
    for(int i = 1; i < n-1; i++){
        int t = gcd(front[i-1], back[i+1]);
        ans = max(ans, t);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include <stdlib.h>
#include <stdio.h>
#include <iostream>

int main(){
  int sum = 0;
  int n;
  std::cin >> n;
  
  int a[n];
  int b[n];
  int c[n];

  for(int i = 0; i < n; i++){
    std::cin >> a[i];
  }
  for(int i = 0; i < n; i++){
    std::cin >> b[i];
  }
  for(int i = 0; i < n-1; i++){
    std::cin >> c[i];
  }

  sum = b[a[0]-1];
  for(int i = 1; i < n; i++){
    sum += b[a[i]-1];
    if(a[i-1]+1 == a[i]){
      sum += c[a[i-1]-1];
    }
  }
  std::cout << sum << "\n";

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <map>
#include <iomanip>

using namespace std;

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

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(16);
    
    solve();

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define set_null(a,n) memset(a,0,sizeof(a))
#define pi acos(-1)
#define ll long long int
#define fr(a,b) for(int i=a;i<b;i++)
#define modulo 1000000007

int main()
{
    int n;
    cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                int x=__gcd(i,j);
                sum+=__gcd(x,k);
            }
        }
    }
    cout<<sum<<endl;

    return 0;
}



Measured memory_bytes: 3632
#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
#include <complex>
 
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>
 
#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++)
#define ALL(c) (c).begin(), (c).end()
#define EACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define RALL(c) (c).rbegin(), (c).rend()
#define ALLA(a,n) ((a)+0), ((a)+n)
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef vector<string> vstring;
typedef vector<double> vdouble;
 
template<class T>void pp(T v,int n){ REP(i,n)cout<<v[i]<< ' ' ; cout << endl; }
template<class T>void pp(T v){ EACH(it,v) cout << *it << ' ' ; cout << endl;  }
template<class T>T& ls(T& a,T b){ if(b<a) a=b; return a; }
template<class T>T& gs(T& a,T b){ if(b>a) a=b; return a; }
inline ll to_i(const string& s){ll n;sscanf(s.c_str(),"%lld",&n);return n;}
inline string to_s(ll n){char buf[32];sprintf(buf,"%lld",n);return string(buf);}

inline void write_bool(bool b, const string &tval, const string &fval) {
  cout << (b ? tval : fval) << endl;
} 
inline void YESNO(bool b) { return write_bool(b, "YES", "NO"); }
inline void YesNo(bool b) { return write_bool(b, "Yes", "No"); }
inline void yesno(bool b) { return write_bool(b, "yes", "no"); }

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

struct Edge { ll src, dst, cost; };
bool operator>(const Edge& a, const Edge& b) {
  return a.cost > b.cost;
}

int main() {
  int n;
  while (cin >> n) {
    vector<vector<Edge>> v(n);
    REP(i,n-1) {
      int s, d, c; cin >> s >> d >> c;
      s--; d--;
      v[s].push_back((Edge) { s, d, c });
      v[d].push_back((Edge) { d, s, c });
    }

    int q, k; cin >> q >> k; k--;
    vll cost(n, 1LL << 60);
    priority_queue<Edge, vector<Edge>, greater<Edge>> qu;
    for (qu.push((Edge){ -1, k, 0}); qu.size(); qu.pop()) {
      Edge e = qu.top();
      if (cost[e.dst] <= e.cost) continue;
      cost[e.dst] = e.cost;

      for (auto &next: v[e.dst]) {
        qu.push((Edge) { e.dst, next.dst, e.cost + next.cost });
      }
    }

    REP(_,q) {
      int a, b; cin >> a >> b; a--; b--;
      cout << cost[a] + cost[b] << endl;
    }
  }
}


Measured memory_bytes: 14768
MOD = 998244353


class Combination:
    #modの宣言をする必要がある。
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % MOD
        self.invmod = [1] * (N + 1)
        #逆元?
        self.invmod[N] = pow(self.fac[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % MOD

    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % MOD * self.invmod[n - k] % MOD


N, M, K = map(int, input().split())
C = Combination(N)

ans = 0
for k in range(K + 1):
    tmp = C.calc(N - 1, N - k - 1) * M * pow(M - 1, N - k - 1, MOD) % MOD
    ans = (ans + tmp) % MOD

print(ans)

Measured memory_bytes: 24508
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int jp[n+1],h[n+1];
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	h[0] = 10000000;
	jp[0] = 0;
	jp[1] = 0;
	for(int i=2;i<=n;i++){
		jp[i] = min( ( abs(h[i]-h[i-1]) + jp[i-1]),( abs(h[i]-h[i-2]) + jp[i-2]));
	}
	cout<<jp[n];
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int arr[1010];
int main()
{
    int N, M;
    cin >> N >> M;
    for(int i=0; i<M; ++i)
    {
        int x, y ;cin>>x>>y;
        arr[x]++;arr[y]++;
    }
    for(int i=1; i<=N; ++i)
        cout <<arr[i] <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

void	solve()
{
	int n;
	cin >> n;
	vector<int> v(n);
	rep(i, n) cin >> v[i];
	int sum = accumulate(all(v), 0);
	int m;
	cin >> m;
	rep(i, m) {
		int p, x;
		cin >> p >> x;
		p--;
		cout << sum - v[p] + x << endl;
	}
}

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

	solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)n; i++)
typedef long long ll;
const ll MOD = 1000000007;
const int nmax = 8;
int graph[nmax][nmax] = {};
int dfs(int v, int N, vector<bool > visited){
  bool all = true;
  REP(i, N){
    if(!visited[i]) {
      all = false;
      break;
    }
  }
  if(all) return 1;

  int ret = 0;
  for(int i = 0; i < N; i++){
    if(graph[v][i] == 1 && visited[i] == false){
      //      cout << "v, i = " << v <<", " << i << endl;
      visited[i] = true;
      ret += dfs(i, N, visited);
      visited[i] = false;
    }
  }
  return ret;
}
int main(){
  int N, M;
  cin >> N >> M ;
  //  int Mat[N][N] = {};
  vector<pair<int, int > > g(M);
  REP(i, M) cin >> g[i].first >> g[i].second;
  REP(i, M) {
    graph[g[i].first - 1][g[i].second - 1] = 1;
    graph[g[i].second - 1][g[i].first - 1] = 1;
  }
  //  REP(i, N){
  //    REP(j, N){
  //      cout << graph[i][j] << "\t";
  //    }
  //    cout << "\n" ;
  //  }
  vector<bool > v(N , false);
  v[0] = true;
  //  REP(i, N) cout << v[i] << "\t";
  cout << endl;
  cout << dfs(0, N, v)<< endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
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; }
const double PI = acos(-1.0);
// cout << fixed << setprecision(14);

bool dp1[4005][16200];
bool dp2[4005][16200];
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

    string S;
    int x, y;
    cin >> S >> x >> y;
    S += "T";
    int W = S.size();
    x += W; // 
    y += W; // 原点を(W,W)として考える
    vector<int> yoko, tate;
    bool xy{}; // 縦方向(y軸)を向いていたらtrue;
    int num = 0;
    bool ans = true;
    rep(i,W){
        if(S[i] == 'T'){
            if(ans){
                x -= num;
                ans = false;
            }
            else if(num != 0){
                if(xy){
                    tate.push_back(num);
                }
                else{
                    yoko.push_back(num);
                }
            }
            num = 0;
            xy = (!xy);
        }
        else{
            ++num;
        }
    }
    int N = tate.size(), M = yoko.size();
    dp1[0][W] = true; // 
    dp2[0][W] = true; // (W,W)が原点のため
    rep(i,N){
        rep(j,16100){
            if(!dp1[i][j]) continue;
            dp1[i+1][j+tate[i]] = true;
            dp1[i+1][j-tate[i]] = true;
        }
    }
    rep(i,M){
        rep(j,16100){
            if(!dp2[i][j]) continue;
            dp2[i+1][j+yoko[i]] = true;
            dp2[i+1][j-yoko[i]] = true;
        }
    }
    if(x < 0 || y < 0){
        cout << "No" << endl;
        return 0;
    }
    if(dp1[N][y] && dp2[M][x]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 66432
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll INF=1e18;

int main(){
    ll n;
    cin >> n;
    map<ll,ll> m;
    rep(i,n){
        ll a;
        cin >> a;
        m[a]++;
    }
    ll ans=0;
    for(auto x:m){
        ll sum=0;
        ll val=x.fi;
        rep(i,3){
            if(m.count(val+i-1)){
                sum+=m[val+i-1];
            }
        }
        ans=max(ans,sum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 7504
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<functional>

#define vec2c vector<vector<char>>
#define vec2i vector<vector<int>>
#define vecc vector<char>
#define vecs vector<string>
#define veci vector<int>
#define rep(i, n) for(int i=0; i < (int)(n); i++)
#define rrep(i, n) for(int i=(int)(n); i>=0;i--)

using namespace std;

int sumDig(int num) {
	int dig, sum = 0;
	while (num) {
		dig = num % 10;
		sum = sum + dig;
		num = num / 10;
	}
	return sum;
}
float calc(float y2, float y1, float x2, float x1, float x) {
	float tmp = (y2 - y1) / (x2 - x1);
	float tmp2 = (x - x1);
	return (tmp * tmp2) + y1;
}
veci inVeci(int n) {
	int in;
	veci vec;
	rep(i, n) {
		cin >> in;
		vec.push_back(in);
	}
	return vec;
}
vecc inVecc( int n) {
	char in;
	vecc vec;
	rep(i, n) {
		cin >> in;
		vec.push_back(in);
	}
	return vec;
}
vecs inVecs(int n) {
	string in;
	vecs vec;
	rep(i, n) {
		cin >> in;
		vec.push_back(in);
	}
	return vec;
}


int main()
{
	int n;
	int in;
	veci vec;

	cin >> n;
	vec = inVeci(n);

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

	cout << abs(vec[0] - vec[vec.size()-1]) << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

int main(){
  int cnt=0,n,i,j,num;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&num);
    if(num==2){
      cnt++;
      continue;
    }
    if(num<2 || num%2==0) continue;
    j=3;
    while(j<=sqrt(num)){
      if(num%j==0){
        cnt--;
        break;
      }
        j=j+2;
      }
    cnt++;
  }
  printf("%d\n",cnt);

  return 0;
}


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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  // 無向(有向)グラフの隣接リスト
  ll n; // n:頂点数 m:辺数
  ll k;
  cin >> n >> k;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
    a.at(i)--;
  }
  
  vector<ll> x(n, -1);
  x.at(0) = k;
  ll nowk = k, nown = 0;
  while (true) {
    nown = a.at(nown);
    if (x.at(nown) != -1) {
      nowk--;
      ll cycle = x.at(nown) - nowk;
      nowk %= cycle;
      while (nowk > 0) {
        nown = a.at(nown);
        nowk--;
      }
      cout << nown + 1 << '\n';
      return 0;
    }
    else {
      nowk--;
      x.at(nown) = nowk;
      if (nowk == 0) {
        cout << nown + 1 << '\n';
        return 0;
      }
    }
  }
}

Measured memory_bytes: 6368
#include <stdio.h>
int main(){
  unsigned int n;
  int i,j;
  unsigned long long int ans = 1;
  unsigned long long int bf_ans = 1;
  unsigned long int max=1000000000000000000;
  //printf("%lu\n",max);
  scanf("%d",&n);
  //printf("%d",n);
  unsigned long long int a[n];


  for(i=0;i<n;i++){
    scanf("%lld",&a[i]);
  }
  for(i=0;i<n;i++){
    if(a[i]==0){
      printf("0\n");
      return 0;
    }
    bf_ans = ans;
    ans *= a[i];
    //printf("%d : %llu\n",i,ans);
    /*if(ans/a[i]!=bf_ans){
      for(j=i;j<n;j++){
        if(a[j]==0){
          printf("0\n");
          return 0;
        }
        printf("-1\n");
        return 0;
    }*/
    if(ans/a[i]!=bf_ans || ans > max || ans < 0){
      for(j=i;j<n;j++){
        if(a[j]==0){
          printf("0\n");
          return 0;
        }
      }
      printf("-1\n");
      return 0;
    }
  }
  printf("%llu\n",ans);
  return 0;
}


Measured memory_bytes: 2508
INF = 10**10 - 1


#指定数分の３つの整数を順番に受けてリストに入力
# スペース区切りの整数入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())

#dpの初期化
dp = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for ww in range(1,Wmax+1):
        if w[i] > ww:
            dp[i][ww] = dp[i-1][ww]        
        else:
            dp[i][ww] = max(dp[i-1][ww],dp[i-1][ww-w[i]]+v[i])
    #print(dp[i])

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)


Measured memory_bytes: 120684
# coding: utf-8
# Your code here!

import collections
N = int(input())
L = [int(i) for i in input().split()]

L = sorted(L)
# print(L)
c = collections.Counter(L)
l = list(c)
# print(c.keys())
# print(len(c))
# print(l)
#print(c.len)
#print("4nokosuu",c[l[2]])

if N < 3:
    print(0)
else:
    cnt = 0
    tmp_cnt = 0
    i_tmp_cnt = 0
    for i in range(len(c)-1):
        j=i+1
        k=i+2
        while j < (len(c)-1):
            while k < (len(c)):
                if l[k] - l[i] < l[j] and l[j] < l[k] + l[i]:
                    # print("cnt++",l[i],l[j],l[k])
                    tmp_cnt += 1 * c[l[k]]
                    # print("c[",l[k],"]=",c[l[k]]," tmp_cnt=",tmp_cnt)
                    k += 1
                else:
                    # print("no",l[i],l[j],l[k])
                    k += 1
            # print("tmp_cnt!!",tmp_cnt)
            tmp_cnt = tmp_cnt * c[l[j]]
            # print("tmp_cnt * c[l[j]]=",tmp_cnt)
            # cnt += tmp_cnt * c[l[i]] * c[l[j]]
            # print("j,k finish.")
            j += 1
            k = j + 1
            i_tmp_cnt += tmp_cnt
            tmp_cnt = 0
            # print("i_tmp_cnt=",i_tmp_cnt)
            # print("\n")
        #cnt += tmp_cnt * c[l[i]] * c[l[j-1]] * c[l[k-1]]
        # print("c[",l[i],"]=",c[l[i]])
        cnt += i_tmp_cnt * c[l[i]]
        tmp_cnt = 0
        i_tmp_cnt = 0
        # print("i finish. cnt=",cnt)
        # print("\n")
        

    print(cnt)

Measured memory_bytes: 68272
import itertools,math,numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
xy = np.array([LI() for _ in range(N)])
sum_norm = 0
dict_norm = {}
for a in itertools.permutations(range(N)):
    for i in range(len(a)-1):
        vector = tuple(xy[a[i+1]]-xy[a[i]])
        if not vector in dict_norm:
            dict_norm[vector] = np.linalg.norm(vector)
            vector_inverse = tuple([vector[0]*-1,vector[1]*-1])
            dict_norm[vector_inverse] = dict_norm[vector]
        sum_norm += dict_norm[vector]
print(sum_norm/math.factorial(N))


Measured memory_bytes: 21476
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl '\n'
//#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define BIT(n) (1LL << (n))
#define TOUPPER(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define TOLOWER(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define FILLZERO(s, n)                      \
    do {                                    \
        ostringstream os;                   \
        os << setw(n) << setfill('0') << s; \
        s = os.str();                       \
    } while (0);
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
#define INIT                               \
    std::cin.tie(nullptr);                 \
    std::ios_base::sync_with_stdio(false); \
    cout << std::fixed << std::setprecision(10);

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using pi = pair<int, int>;
template <typename T>
using Pq = priority_queue<T>;
template <typename T>
using pQ = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
vector<T> make_vec(size_t a, T n) { return vector<T>(a, n); }
template <typename T, typename... Ts>
auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); }
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;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

signed main() {
    INIT;
    cin >> A >> B >> C >> D;
    cout << max(max(A * C, A * D), max(B * C, B * D)) << endl;
}

Measured memory_bytes: 3644
n,m,x = gets.chomp.split(" ").map(&:to_i)
a = gets.chomp.split(" ").map(&:to_i)
down = 0
up = 0
m.times do |i|
  if a[i] < x
    down += 1
  else
    up += 1
  end
end
puts [down,up].min

Measured memory_bytes: 14400
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static boolean solve() {
		int t = in.nextInt();
		int p = in.nextInt();
		int r = in.nextInt();
		if (t + p + r == 0) return false;

		int[][] a = new int[t][3];
		for (int i=0; i<t; i++) {
			a[i][2] = i+1;
		}
		int[][] wrong = new int[t][p];

		for (int i=0; i<r; i++) {
			int tid = in.nextInt() - 1;
			int pid = in.nextInt() - 1;
			int time = in.nextInt();
			String s = in.next();
			if (wrong[tid][pid] == -1) continue;
			if ("CORRECT".equals(s)) {
				a[tid][0]++;
				a[tid][1] += time + 1200*wrong[tid][pid];
				wrong[tid][pid] = -1;
			} else {
				wrong[tid][pid]++;
			}
		}

		Arrays.sort(a, new Comparator<int[]>(){
			public int compare(int[] a, int[] b) {
				if (a[0] != b[0]) return b[0] - a[0];
				if (a[1] != b[1]) return a[1] - b[1];
				return a[2] - b[2];
			}
		});

		for (int i=0; i<t; i++) {
			out.println(a[i][2]+" "+a[i][0]+" "+a[i][1]);
		}


		return true;
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		while(solve());
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

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

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

int N;
int GA, GB, SA, SB, BA, BB;
ll DP[5000 * 5000 + 2];

int main(){
    cin >> N;
    cin >> GA >> SA >> BA;
    cin >> GB >> SB >> BB;

    memset(DP, 0, sizeof(DP));
    for(ll i=1;i<=N;i++){
        ll G = 0, S = 0, B = 0;

        if(GA <= i)    G = DP[i-GA] + GB;
        if(SA <= i)    S = DP[i-SA] + SB;
        if(BA <= i)    B = DP[i-BA] + BB;

        // cout << G << ", " << S << ", " << B << endl;

        DP[i] = max( {i, G, S, B} );
    }

    /*
    for(int i=0;i<=N;i++)   cout << DP[i] << ", ";
    cout << endl;
    */

    int D = DP[N];
    memset(DP, 0, sizeof(DP));
    for(ll i=1;i<=D;i++){
        ll G = 0, S = 0, B = 0;

        if(GB <= i)    G = DP[i-GB] + GA;
        if(SB <= i)    S = DP[i-SB] + SA;
        if(BB <= i)    B = DP[i-BB] + BA;

        DP[i] = max( {i, G, S, B} );
    }

    /*
    for(int i=0;i<=D;i++)   cout << DP[i] << ", ";
    cout << endl;
    */

    cout << DP[D] << endl;
}

Measured memory_bytes: 195712
n = int(input())
d = len(bin(n)) - 2
mod = 10**9 + 7
dp = [[0 for j in range(3)] for i in range(d+1)]
dp[d][0] = 1
for i in range(d):
    k = d - 1 - i
    for j in range(3):
        if j == 0:
            if (n >> k) & 1:
                dp[k][0] += dp[k+1][0]
                dp[k][1] += dp[k+1][0]
            else:
                dp[k][0] += dp[k+1][0]
        elif j == 1:
            if (n >> k) & 1:
                dp[k][1] += dp[k+1][1]
                dp[k][2] += dp[k+1][1] * 2
            else:
                dp[k][0] += dp[k+1][1]
                dp[k][1] += dp[k+1][1]
                dp[k][2] += dp[k+1][1]
        else:
            dp[k][2] += dp[k+1][2] * 3
        map(lambda x:x%mod, dp[k])
print(sum(dp[0]) % mod)

Measured memory_bytes: 3064
H, W = map(int, input().split())
s = [['.'] * (W + 2)] + [list('.' + input() + '.') for _ in range(H)] + [['.'] * (W + 2)]
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if s[h][w] == '.':
            continue
        if s[h - 1][w] == s[h + 1][w] == s[h][w - 1] == s[h][w + 1] == '.':
            print('No')
            exit()
print('Yes')


Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<list>
#include<bitset>
#include<cctype>
#include<iomanip>
using namespace std;
const int N = 100;
typedef long long ll;
#define PI 3.1415927

int main(){
	char a,b;
	while(cin>>a>>b){
		if(a>b)
			cout<<">"<<endl;
		else if(a==b)
			cout<<"="<<endl;

		else if(a<b)
			cout<<"<"<<endl;		
		}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep0(i,n) for(i=0;i<n;i++)
#define rep(i,n) for(i=1;i<=n;i++)
#define reps(i,a,n) for(i=a;i<=n;i++)
#define mem(ara,n) memset(ara,n,sizeof(ara))
#define memb(ara) memset(ara,false,sizeof(ara))
#define all(x) (x).begin(),(x).end()
#define fast ios_base:: sync_with_stdio( false ); cin.tie(0); cout.tie(0);
#define eb              emplace_back
#define em              emplace
#define pb              push_back
#define Mp              make_pair
#define ff              first
#define ss              second
#define mod 1000000007
# define M_PI          3.141592653589793238462643383279502884L
typedef long long ll;
using namespace std;

const int M = (int)(2e6 + 239);

int getnum(string a)
{
    int i,p=0;
    rep0(i,a.size())
    {
        p*=10;
        p+=a[i]-'0';
    }
    return p;
}

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

    double a;
    cin>>a;
    a = 2*M_PI*a;
    printf("%.10f\n",a);
}


Measured memory_bytes: 3808
from itertools import permutations
from math import factorial


# メインプログラム
def func(N, lst):

    # N! を求める
    N_fact = factorial(N)

    # lst から座標のすべての組合せを求める。
    perm_grid_xy = permutations(lst)

    # すべての組合せを全探索して、総合距離を計算する
    total_dist = total_distance(N, perm_grid_xy)

    # 平均距離 = 総合距離 / N!
    average_dist = total_dist / N_fact

    return average_dist


def total_distance(N, perm_grid_xy):
    
    ret = 0
    
    for grid_xy in perm_grid_xy:
        tmp = sum(
            ((grid_xy[i][0] - grid_xy[i+1][0]) ** 2 
            + (grid_xy[i][1] - grid_xy[i+1][1]) ** 2) ** 0.5 
            for i in range(N-1)
            )
        ret += tmp

    return ret


if __name__ == "__main__":
    N = int(input())
    lst = [tuple(map(int, input().split())) for _ in range(N)]
    print(func(N, lst))

Measured memory_bytes: 3188
import java.io.*;
 import java.util.*;
public class Main{
  static public void main(String args[]){
 try {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String buf = br.readLine();

String[] tmp = buf.split(" ",0);

Calculate calc = new Calculate(Integer.parseInt(tmp[0]),
								Integer.parseInt(tmp[1]));
	calc.show();
    } catch(IOException e) {
      System.err.println(e.getMessage());
    }
}
}

class Calculate{
	int a;
	int b;
  Calculate(int x, int y) {
  	a=x;
	b=y;
  }
	public void show(){
	System.out.printf("%d %d %.6f", a/b, a%b, (double)a/b);
}

}

Measured memory_bytes: 16928
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
//constexpr ll MOD = 998244353;
//constexpr ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
constexpr ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)

int main()
{
  ll N, M;
  cin >> N >> M;

  cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define v vector<ll>
#define vv vector<v>
#define p pair<ll,ll>
ll inf=1e17;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,w;
    cin>>n>>w;
    v weight(n+1,-1),value(n+1,-1);
    for (int i=1; i<=n; i++)
        cin>>weight[i]>>value[i];
    int LIM=1e5+10;
    vv dp(n+1,v(LIM+1,-1));
    dp[0][0]=w;
    for (int i=1; i<=n; i++)
    {
        dp[i][0]=w; 
        for (int j=1; j<=LIM; j++)
        {
            dp[i][j]=dp[i-1][j];
            if (j>=value[i])
                dp[i][j]=max(dp[i][j],dp[i-1][j-value[i]]-weight[i]);
        }
    }
    ll ans=0;
    for (int i=1; i<=LIM; i++)
        if (dp[n][i]!=-1)
            ans=i;
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 80256
# A = [list(map(int, input().split())) for _ in range(3)]
# k = int(input())
# B = [int(input()) for _ in range(n)]
# X = list(map(int, input().split()))
# a, b = map(int, input().split())
S = input()
n = len(S)
judge = True
if S != S[::-1]:
    judge = False
for i, j in zip(S[:n//2], S[n//2+1:]):
    if i != j:
        judge = False
print("Yes") if judge else print("No")


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

int main()
{
	long long int N;
	cin >> N;

	vector<long long int> a(N);
	set<long long int> checkSet;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
		checkSet.insert(a[i]);
	}

	if (N % 3 == 0)
	{
		auto itr = checkSet.begin();
		if (checkSet.size() == 3)
		{
			int cnt1 = count(a.begin(), a.end(), *itr);
			int cnt2 = count(a.begin(), a.end(), *(++itr));
			int cnt3 = count(a.begin(), a.end(), *(++itr));

			if ((*(--(--itr)) ^ *(++itr)) == *(++itr) && cnt1 == cnt2 && cnt2 == cnt3)
			{
				cout << "Yes" << endl;

				return 0;
			}
		}
		else if (checkSet.size() == 2)
		{
			int cnt1 = count(a.begin(), a.end(), *itr);
			int cnt2 = count(a.begin(), a.end(), *(++itr));

			int min;
			if (cnt1 < cnt2)
			{
				if (cnt1 * 2 == cnt2 && *(--itr) == 0)
				{
					cout << "Yes" << endl;

					return 0;
				}
			}
			else
			{
				if (cnt2 * 2 == cnt1 && *(itr) == 0)
				{
					cout << "Yes" << endl;

					return 0;
				}
			}
		}
	}

	if (checkSet.size() == 1)
	{
		if (a[0] == 0)
		{
			cout << "Yes" << endl;

			return 0;
		}
	}

	cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 4480
num      = int(input())
is_valid = True
words    = []
words.append(input())
for i in range(1, num):
    word = input()
    words.append(word)
    if words[i-1][-1] != word[0]:
        print('No')
        quit()

if len(words) != len(set(words)):
    print('No')
else:
    print('Yes')

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
typedef struct{
    long a,b;
}data;
int cmp(const void *c,const void *d){
    return ((data*)c)->a-((data*)d)->a;
}
int main(void){
    long n,i,k;
    data p[100001];
    scanf("%ld %ld",&n,&k);
    for(i=0;i<n;i++){
        scanf("%ld %ld",&p[i].a,&p[i].b);
    }
    qsort(p,n,sizeof(p[0]),cmp);
    for(i=0;i<n;i++){
        k-=p[i].b;
        if(k<=0)break;
    }
    printf("%ld\n",p[i].a);
    return 0;
    
}

Measured memory_bytes: 3324
import java.io.*;
public class Main {
    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line;
        int a;
        int[] x;
        int i,j;
        x = new int[10000];
        try{
        i=1;
        while(true){
        line = reader.readLine();
        a = Integer.parseInt(line);
        if(a == 0) break;
        x[i-1]=a;
        ++i;
        }
        for(j=0;j<i-1;j++){
        System.out.println("Case "+(j+1)+": "+x[j]);
        }
        }catch (NumberFormatException e) {
            System.out.println(e);
        } catch (IOException e) {
            System.out.println(e);
        }

    
    }
}



Measured memory_bytes: 32308
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

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

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    set<char> s;
    REP(i,n){
        char c;cin>>c;
        s.insert(c);
    }
    string ans="";
    s.size()==4? ans="Four":ans="Three";
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

const int mod = 1000000007;
struct mint{
	ll x;
	mint(ll x = 0):x((x%mod+mod)%mod){}
	mint operator-() const{return mint(-x);}
	mint& operator+=(const mint a){
		if((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a){
		if((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a){
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const{
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const{
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const{
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const{
		if(!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if(t&1) a *= *this;
		return a;
	}
	mint inv() const{
		return pow(mod-2);
	}
	mint& operator/=(const mint a){
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const{
		mint res(*this);
		return res/=a;
	}
	bool operator==(const mint a){
		return x == a.x;
	}
};

istream& operator>>(istream& is, const mint& a){return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a){return os << a.x;}

// 2^n
mint f(int n){
	if(n == 0) return 1;
	mint x = f(n/2);
	x *= x;
	if(n%2 == 1) x *= 2;
	return x;
}

// nCa
mint choose(int n, int a){
	mint x = 1, y = 1;
	rep(i,a){
		x *= n-i;
		y *= i+1;
	}
	return x / y;
}

struct Combination{
	vector<mint> fact, ifact;
	Combination(int n):fact(n+1),ifact(n+1){
		assert(n < mod);
		fact[0] = 1;
		for(int i = 1; i <= n; i++) fact[i] = fact[i-1]*i;
		ifact[n] = fact[n].inv();
		for(int i = n; i >= 1; i--) ifact[i-1] = ifact[i]*i;
	}
	mint operator()(int n, int k){
		if(k < 0 || k > n) return 0;
		return fact[n]*ifact[k]*ifact[n-k];
	}
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    Combination comb(n*m+1);
    mint ans = 0;
    rep(i,n){
        ans += comb(n*m-2, k-2) * (mint)(i) * (mint)(n-i) * (mint)(m) * (mint)(m);
    }
    rep(j,m){
        ans += comb(n*m-2, k-2) * (mint)(j) * (mint)(m-j) * (mint)(n) * (mint)(n);
    }
    cout << ans.x << endl;
    return 0;
}


Measured memory_bytes: 6372
#include <iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+1];
	a[0]=0;
	int s=0;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		if(a[i]>a[i-1])  s+=a[i]-a[i-1];
	}
	cout<<s;
}

Measured memory_bytes: 256