akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main()
{
    vector<vector<int>>masu(3, vector<int>(3, 0));

    for (int i=0; i<3; i++) {
        int c1, c2, c3;
        cin >> c1 >> c2 >> c3;
        masu[i][0] = c1;
        masu[i][1] = c2;
        masu[i][2] = c3;
    }

    bool say_takahashi = true;
    for (int i=0; i<3; i++) {
        int add_index = i + 1;
        if (add_index == 3) {
            add_index = 0;
        }

        int one = masu[i][0] - masu[add_index][0];
        int two = masu[i][1] - masu[add_index][1];
        int three = masu[i][2] - masu[add_index][2];
        if (one != two || two != three) {
            say_takahashi = false;
            break;
        }
    }

    for (int j=0; j<3; j++) {
        int add_index = j + 1;
        if (add_index == 3) {
            add_index = 0;
        }

        int one = masu[0][j] - masu[0][add_index];
        int two = masu[1][j] - masu[1][add_index];
        int three = masu[2][j] - masu[2][add_index];
        if (one != two || two != three) {
            say_takahashi = false;
            break;
        }
    }

    if (say_takahashi) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

typedef long long ll;

using namespace std;

void solve() {
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N-1);
    REP(i, N) {
        int a;
        cin >> a;
        a--;
        A[i] = a;
    }
    REP(i, N) cin >> B[i];
    REP(i, N-1) cin >> C[i];

    int ans = 0;
    int prev = -111;
    REP(i, N) {
        ans += B[A[i]];
        if (prev+1 == A[i]) ans += C[A[i]-1];
        prev = A[i];
    }
    print(ans);

}

signed main() {
    solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <math.h>
using namespace std;
#pragma warning(disable : 4996)


int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int a, b;
	cin >> a >> b;
	cout << 6 - a - b;
}

Measured memory_bytes: 256
N = int(input())
K = int(input())

N_ = str(N)
n = len(N_)

dp = [[[0]*2 for i in range(5)] for j in range(110)]

dp[0][0][0] = 1
dp[0][0][1] = 0

for i in range(n):
  for j in range(4):
    for k in range(2):
      nd = int(N_[i])
      for d in range(10):
        ni = i+1
        nj = j
        nk = k
        if d != 0:
          nj += 1
        if nj >3:
          continue
        if k == 0:
          if d > nd:
            continue
          elif d < nd:
            nk = 1
          else:
            pass
        dp[ni][nj][nk] += dp[i][j][k]
        
print(sum(dp[n][K]))

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int n,s,q,a[100005],sum;
int main(){
cin>>n>>s>>q;
for(int k=1;k<=q;k++){
        int b;
        cin>>b;
    a[b]++;
}
for(int k=1;k<=n;k++){
   if(s-q+a[k]>0)
    cout<<"Yes"<<endl;
   else cout<<"No"<<endl;
}
return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll n;

int main(){
    cin >> n;
    vector<ll> ans(n+1);
    ans[0] = 0;
    ll of = 0;
    rep(i,n){
        ll a;
        cin >> a;
        ans[i + 1] = a - ans[i];
    }
    rep(i,n){
        ll num = ans[i];
        // cout << num << endl;
        if(i%2 == 0)num += (ans[n] - ans[0]) / 2;
        else num -= (ans[n] - ans[0]) / 2;
        cout << 2*num << " ";
    }
    cout << endl;
}

Measured memory_bytes: 2048
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#l = list(map(int, input().split()))

k = int(input())
a, b = map(int, input().split())

for i in range(a,b+1):
    if (i%k == 0):
        print("OK")
        exit()

print("NG")


Measured memory_bytes: 9148
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pb push_back
#define pii pair<long long,long long>
#define endl '\n'
#define N 300001
int mod=1000000007;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
vector<int> parent(N),sz(N),indegree(N),vis(N); char st[N];
vector<int> adj[N];
int modexp(int x,int n,int M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)        
        return modexp((x*x)%M,n/2,M);
    else                             
        return (x*modexp((x*x)%M,(n-1)/2,M))%M;
}
void make_set(int s)
{
    parent[s]=s;
    sz[s]=1;
}
int find_parent(int p)
{
    if(p==parent[p])
    return p;
    return parent[p]=find_parent(parent[p]);
}
void union_set(int a,int b)
{
    a=find_parent(a);b=find_parent(b);
    if(a!=b)
    {
        if(a<b)
        swap(a,b);
        parent[b]=parent[a];
        sz[a]+=sz[b];
    }
}
bool comp(const pii a, const pii b)
{
    if(a.se==b.se)
    return a.fi<b.fi;
    return a.se<b.se;
}
vector<vector<int>> dp,v;
void solve()
{
    int n; cin>>n;
    int p=100; int x=0;
    while(n>p)
    {
        p=p*(1.01);
        x++;
    }
    cout<<x;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test; test=1;
    while(test--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 19444
{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Data.List

fact n = product [1..n]

solve :: Int -> VU.Vector (Int, Int) -> Double
solve !n !vs = (/ fromIntegral (fact n)) $ sum $ map (dist 0) $ permutations [0 .. n - 1]
  where
    dist !acc (i:j:ks) =
      let (x1,y1) = vs VU.! i
          (x2,y2) = vs VU.! j
      in dist (sqrt (fromIntegral $ (x1-x2)^2 + (y1-y2)^2) + acc) (j:ks)
    dist !acc _ = acc

main = do
  let readInt = fmap (second B.tail) . B.readInt

  n   <- (VU.! 0) . VU.unfoldrN 1 readInt <$> B.getLine
  xys <-
    VU.replicateM n
    $   (\vec -> (vec VU.! 0, vec VU.! 1))
    .   VU.unfoldrN 2 readInt
    <$> B.getLine

  print $ solve n xys


Measured memory_bytes: 1916
use std::io;
fn main() {
    let mut l1 = String::new();
    let mut l2 = String::new();
    let stdin = io::stdin();
    stdin.read_line(&mut l1).unwrap();
    stdin.read_line(&mut l2).unwrap();
    let trimed = l1.trim_end();
    let trimed2 = l2.trim_end();
    let mut itr = trimed.split_ascii_whitespace();
    let mut itr2 = trimed2.split_ascii_whitespace();
    let n = itr.next().unwrap().parse::<i64>().unwrap();

    let mut vec = vec![0; n as usize];
    for x in 0..n - 1 {
        let a = itr2.next().unwrap().parse::<i64>().unwrap();
        vec[(a - 1) as usize] = vec[(a - 1) as usize] + 1;
    }

    for x in &vec {
        println!("{}", x);
    }
}


Measured memory_bytes: 3984
#include<stdio.h>
#include<stdlib.h>
int main() {
    int a, b, m, min =10000000;
    int* an;
    int* bn;
    scanf("%d%d%d", &a, &b, &m);
    an = (int*)malloc(sizeof(int) * (a + 1));
    bn = (int*)malloc(sizeof(int) * (b + 1));

    for (int i = 1; i <= a; i++) { scanf("%d", &an[i]); }
    for (int i = 1; i <= b; i++) { scanf("%d", &bn[i]); }


    for (int i = 0; i < m; i++) {
        int d1, d2, d3;
        scanf("%d%d%d", &d1, &d2, &d3);
        int cost = an[d1] + bn[d2] - d3;
        if (cost < min) { min = cost; }
    }
    int bmin = bn[1],amin=an[1];
    for (int i = 2; i <= b; i++) {
        if (bn[i] < bmin) { bmin = bn[i]; }
    }
    for (int i = 2; i <= a; i++) {
        if (an[i] < amin) { amin = an[i]; }
    }

    if (min > amin + bmin) { min = amin + bmin; }

    printf("%d", min);
    return 0;
}

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

int main() {
    int n, m, x;
    cin >> n >> m >> x;

    vector<int> c(n);
    vector<vector<int>> a(n, vector<int>(m));
    int max_money = 0;
    for (int i = 0; i < n; i++) {
        cin >> c.at(i);
        max_money += c.at(i);

        for (int j = 0; j < m; j++) {
            cin >> a.at(i).at(j);
        }
    }

    int flag = 1;
    for (int i = 0; i < m; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += a.at(j).at(i);
        }
        if (sum < x) flag = 0;
    }
    if (flag == 0) {
        cout << "-1" << endl;
        return 0;
    }

    int min_money = max_money;
    for (int tmp = 0; tmp < (1 << n); tmp++) {
        bitset<12> s(tmp);
        //cout << s << endl;
        int money = 0;
        vector<int> skills(m);
        for(int i = 0; i < n; i++) {
            if (s.test(i)) {
                money += c.at(i);
                for (int j = 0; j < m; j++) {
                    skills.at(j) += a.at(i).at(j);
                }
            }
        }
        
        flag = 1;
        for (int j = 0; j < m; j++) {
            if (skills.at(j) < x) flag = 0;
        }
        //cout << money << endl;
        if (flag == 1) {
            
            min_money = min(money, min_money);
        }
    }

    cout << min_money << endl;
}

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

using namespace std;

#define forsn(i, s, n) for(int i=s;i<int(n);i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) v.begin(), v.end()

typedef long long tint;

const tint MOD = 1000000007;

int main(){
	int n, m; cin >> n >> m;
	vector<string> mat (n);
	vector<vector<char>> tab (n, vector<char> (m));
	forn(i, n){
		cin >> mat[i];
		forn(j, m){
			tab[i][j] = mat[i][j];
		}
	}
	vector<vector<int>> dp (n, vector<int> (m, 0));
	if(tab[0][0] == '.') dp[0][0] = 1;
	forn(i, n){
		forn(j, m){
			if(i == 0 && j == 0) continue;
			if(tab[i][j] == '#') continue;
			int x = i-1, y = j-1;
			if(0<=x && x < n){
				dp[i][j]+=dp[x][j]%MOD;
			}
			if(0<=y && y<m){
				dp[i][j]+=dp[i][y]%MOD;
			}
		}
	}
	cout << dp[n-1][m-1]%MOD << endl;
}



Measured memory_bytes: 6272
#include <stdio.h>
void change(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
int main() {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    int tmp;
    if (a > b) change(&a, &b);
    if (b > c) change(&b, &c);
    if (a > b) change(&a, &b);
    printf("%d %d %d\n", a, b, c);
    return 0;
}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    ll n,k,A[200001],sum=0;
    cin>>n>>k;
    rep(i,n){
        cin>>A[i];
        if(A[i]>0) sum+=A[i];
    }
    ll m=1e18,a=0,b=0;
    rep(i,n-k+1){
        if(i==0) rep(j,k) a+=A[j]*(A[j]<0),b+=A[j]*(A[j]>0);
        else{
            a=a-A[i-1]*(A[i-1]<0)+A[i+k-1]*(A[i+k-1]<0);
            b=b-A[i-1]*(A[i-1]>0)+A[i+k-1]*(A[i+k-1]>0);
        }
        m=min({m,-a,b});
    }
    cout<<sum-m;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main(){
  int w,n,i,j,max,mi,a,b,k;
  for(k=1;scanf("%d",&w),w;k++){
    int m[1002][1002]={0};
    scanf("%d",&n);
    for(i=1;i<=n;i++){
      scanf("%d,%d",&a,&b);
      for(j=1;j<=w;j++){
	m[i][j]=m[i-1][j];
	if(j<b)continue;
	if(m[i][j]<m[i-1][j-b]+a)m[i][j]=m[i-1][j-b]+a;
      }
    }
    for(i=max=0;i<=w;i++){
      if(max<m[n][i]){
	max=m[n][i];
	mi=i;
      }
    }
    printf("Case %d:\n%d\n%d\n",k,max,mi);
  }
  return 0;
}
    
    

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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> r(n);
    
    for(int i=0;i<n;i++) cin >> r[i];
    
    int maxv =r[1]-r[0],minv =r[0];
    for(int i=1;i<n;++i) {
        if(maxv<r[i]-minv) maxv =r[i]-minv;
        if(minv>r[i]) minv = r[i];
    }
    cout << maxv << endl;
    
    return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<ll> x(n), y(n);
  vector<char> d(n);
  vector<ll> dx(n), dy(n);
  rep(i, n) {
    cin >> x[i] >> y[i] >> d[i];
    x[i] *= 2;
    y[i] *= 2;
    if (d[i] == 'L') dx[i] = -1;
    if (d[i] == 'R') dx[i] = 1;
    if (d[i] == 'U') dy[i] = 1;
    if (d[i] == 'D') dy[i] = -1;
  }
  pair<ll, int> L1(1e18, 0);
  pair<ll, int> R1(-1e18, 0);
  pair<ll, int> D1(1e18, 0);
  pair<ll, int> U1(-1e18, 0);
  pair<ll, int> L2(1e18, 0);
  pair<ll, int> R2(-1e18, 0);
  pair<ll, int> D2(1e18, 0);
  pair<ll, int> U2(-1e18, 0);
  pair<ll, int> L3(1e18, 0);
  pair<ll, int> R3(-1e18, 0);
  pair<ll, int> D3(1e18, 0);
  pair<ll, int> U3(-1e18, 0);

  rep(i, n) {
    if (d[i] == 'L') L1 = min(L1, make_pair(x[i], i));
    if (d[i] == 'R') R1 = max(R1, make_pair(x[i], i));
    if (d[i] == 'D') D1 = min(D1, make_pair(y[i], i));
    if (d[i] == 'U') U1 = max(U1, make_pair(y[i], i));
    if (d[i] == 'R') L2 = min(L2, make_pair(x[i], i));
    if (d[i] == 'L') R2 = max(R2, make_pair(x[i], i));
    if (d[i] == 'U') D2 = min(D2, make_pair(y[i], i));
    if (d[i] == 'D') U2 = max(U2, make_pair(y[i], i));
    if (d[i] == 'U' || d[i] == 'D') L3 = min(L3, make_pair(x[i], i));
    if (d[i] == 'U' || d[i] == 'D') R3 = max(R3, make_pair(x[i], i));
    if (d[i] == 'L' || d[i] == 'R') D3 = min(D3, make_pair(y[i], i));
    if (d[i] == 'L' || d[i] == 'R') U3 = max(U3, make_pair(y[i], i));
  }
  auto f = [&](ll t) {
    ll x1 = 1e18;
    ll x2 = -1e18;
    ll y1 = 1e18;
    ll y2 = -1e18;
    x1 = min(x1, x[L1.second] + dx[L1.second] * t);
    x1 = min(x1, x[L2.second] + dx[L2.second] * t);
    x1 = min(x1, x[L3.second] + dx[L3.second] * t);
    
    x2 = max(x2, x[R1.second] + dx[R1.second] * t);
    x2 = max(x2, x[R2.second] + dx[R2.second] * t);
    x2 = max(x2, x[R3.second] + dx[R3.second] * t);

    y1 = min(y1, y[D1.second] + dy[D1.second] * t);
    y1 = min(y1, y[D2.second] + dy[D2.second] * t);
    y1 = min(y1, y[D3.second] + dy[D3.second] * t);
    
    y2 = max(y2, y[U1.second] + dy[U1.second] * t);
    y2 = max(y2, y[U2.second] + dy[U2.second] * t);
    y2 = max(y2, y[U3.second] + dy[U3.second] * t);

    return (x2-x1)*(y2-y1);
  };
  ll ans = 9e18;
  for (ll i = 0; i <= 400000000; i++) {
    ans = min(ans, f(i));
  }
  cout << ans / 4 << '.';
  cout << vector<string>{"00", "25", "50", "75"}[ans % 4] << endl;
}


Measured memory_bytes: 3456
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);


    private static class Battle {
        public Battle(int a, int b) {
            this.a = a;
            this.b = b;
        }

        int a;
        int b;
    }

    public static void main(String[] args) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        PriorityQueue<Battle> queue = new PriorityQueue(new MyComparator());
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            queue.add(new Battle(a, b));
        }
        int answer = 1;
        int lastB = queue.poll().b;
        while (queue.size() > 0) {
            Battle battle = queue.poll();
            if (battle.a < lastB && lastB <= battle.b) {
                continue;
            } else {
                answer++;
                lastB = battle.b;
            }
        }

        System.out.println(answer);
    }

    static class MyComparator implements Comparator<Battle> {

        @Override
        public int compare(Battle o1, Battle o2) {
            if (o1.b < o2.b) {
                return -1;
            } else if (o1.b > o2.b) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}



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

#define repfrom(i, from, n) for (ll i = (from); i < (n); i++)
#define rep(i, n) repfrom(i, 0, n)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)

using namespace std;

using ll = long long;
using p  = pair<ll, ll>;
using uc = unsigned char;
constexpr ll INF = 1LL << 62;
constexpr ll MOD = 1e9 + 7;

ll how_many_look(vector<ll> A) {
    ll higher = 0;
    ll ret = 0;
    for (auto a : A) {
        if (higher < a) {
            higher = a;
            ret++;
        }
    }
    
    return ret;
}

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N, K;
    cin >> N >> K;
    
    vector<ll> A(N);
    for (auto&& a : A) {
        cin >> a;
    }
    
    ll ans = INF;
    for (ll i = 0; i < (1 << (N - 1)); i++) {
        bitset<14> bs(i);
        if (bs.count() != K - 1) {
            continue;
        }
        
        auto B = A;
        vector<ll> idxes;
        idxes.push_back(0);
        for (ll j = 0; j < N - 1; j++) {
            if (bs[j]) {
                idxes.push_back(j + 1);
            }
        }
        
        ll cost = 0;
        for (ll j = 1; j < idxes.size(); j++) {
            ll higher = 0;
            for (ll k = 0; k < idxes[j]; k++) {
                higher = max(higher, B[k]);
            }
            if (higher >= B[idxes[j]]) {
                cost += higher + 1 - B[idxes[j]];
                B[idxes[j]] = higher + 1;
            }
        }
        
        ans = min(ans, cost);
    }
    
    cout << ans << endl;
    
    return 0;
}


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

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

	int a,b;

	cin >> a >> b;

	int x = max(0,a-2*b);

	cout << x << '\n';

	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
	"os"
)

func main() {
	var A, B, i int

	fmt.Scanf("%v %v", &A, &B)

	if (A+B)%2 != 0 {
		fmt.Println("IMPOSSIBLE")
		os.Exit(0)
	}

	for {
		if math.Abs(float64(A-i)) == math.Abs(float64(B-i)) {
			fmt.Println(i)
			break
		}
		i++
	}

}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
typedef long long ll;

int main() {
    string S; cin >> S;
    int ans = 0;
    int n = S.size()-1;
    int N = S.size() / 2;
    for(int i = 0; i < N; i++){
        if(S[i] != S[n-i]) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
#define all(a) (a).begin(),(a).end()
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0;i < (n);i++)
#define rep2(i,n) for(ll i = 0;i < (n);i++)
#define rep3(i,a,b) for(ll i = (a);i < (b);i++)
#define rep4(i,a,b,c) for(ll i = (a);i < (b);i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n)-1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n)-1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (a)-1;i >= (b);i--)
#define rrep4(i,a,b,c) for(ll i = (a)-1;i >= (b);i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define SHOW(x) cout << #x << ": " << x << endl;
template<class T> ll sumArr(const T& a){ return accumulate(all(a), 0LL);}
template<class T> auto minArr(const T& a){ return *min_element(all(a));}
template<class T> auto maxArr(const T& a){ return *max_element(all(a));}
template<class T> void DEBUG_PRINT(T tmp){cout<<tmp<<endl;}
template<class T1,class... T2> void DEBUG_PRINT(T1 tmp,T2... tmp2){cout<<tmp<<" ";DEBUG_PRINT(tmp2...);}
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

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

    int n,k,ans = 0;
    cin>>n>>k;
    vector<int>p(n);
    rep(i,n)cin>>p[i];
    sort(all(p));
    rep(i,k)ans += p[i];
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!$BDs=P;~$K%3%a%s%H%"%&%H(B!!
#ifdef DEBUG_
#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

    template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int mod = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};


signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);
    VI ans(4);
    int N; cin >> N;
    REP(i,N){
        string s;
        cin >> s;
        if(s == "AC") ans[0]++;
        if(s == "WA") ans[1]++;
        if(s == "TLE") ans[2]++;
        if(s == "RE") ans[3]++;
    }

    cout << "AC x " << ans[0] << endl;
    cout << "WA x " << ans[1] << endl;
    cout << "TLE x " << ans[2] << endl;
    cout << "RE x " << ans[3] << endl;


}

Measured memory_bytes: 3656
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
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;
	string s;
	cin >> n >> s;
	
	vector<int> w(n+1), e(n+1);
	w[0] = 0;
	e[0] = 0;
	REP(i,n){
		w[i+1] = w[i];
		e[i+1] = e[i];
		if(s[i]=='W') w[i+1]++;
		if(s[n-1-i]=='E') e[i+1]++;
	}
	
	int ans=1000000;
	REP(i,n){
		chmin(ans, w[i+1]+e[n-i]-1);
	}
	
	cout << ans << endl;
	
	
	
	return 0;
}

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

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

    int n;
    cin >> n;
    hash<string> hs;
    map<int, int> mp;
    int N = 0;
    map<string, int> id;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        if (id.count(s))
            mp[id[s]]++;
        else {
            id[s] = N++;
            mp[id[s]]++;
        }
    }
    long long ans = 0;
    for (auto& p : mp) {
        ans += 1LL * p.second * (p.second - 1) / 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 15872
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll now = 1000;
    ll kabu = 0;
    int upper = 0;
    for(int i = 0; i < N; i++) {
        if(i + 1 == N || ((upper == 1 || upper == 0) && A[i] > A[i + 1])) {
            now += kabu * A[i];
            kabu = 0;
        } else if((upper == -1 || upper == 0) && A[i] < A[i + 1]) {
            ll num = now / A[i];
            now -= A[i] * num;
            kabu += num;
        }
        if(i + 1 < N && A[i] < A[i + 1]) {
            upper = 1;
        } else if(i + 1 < N && A[i] > A[i + 1]) {
            upper = -1;
        } else {
            upper = 0;
        }
    }
    cout << now << endl;
    return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>
int main(void)
{
    int a[20];
    int q,i,k,l;
    k=0;
    scanf("%d",&q);
    for(i=0;i<q;i++){
    scanf("%d",&a[i]);}
    
    for(i=1;i<q-1;i++){
    if(a[i]<a[i+1]&&a[i]>a[i-1]){
    k++;}else if(a[i]>a[i+1]&&a[i]<a[i-1]){
    k++;}
    }
    printf("%d",k);
    return 0;
    }


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

void draw(int H, int W) {
    for (int i = 0; i < H; i++) {
        if (i == 0 || i == H - 1) {
            for (int j = 0; j < W; j++) {
                cout << "#";
            }
        } else {
            for (int j = 0; j < W; j++) {
                if (j == 0 || j == W - 1) {
                    cout << "#";
                } else {
                    cout << ".";
                }
            }
        }
        cout << endl;
    }
    cout << endl;
}

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

    int H, W;
    while (true) {
        cin >> H >> W;
        if (H == 0 && W == 0) {
            break;
        } else {
            draw(H, W);
        }
    }
}


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

using namespace std;

int main( )
{
	string str;
	int i;
	
	getline(  cin, str );
	
	for( i=0; '\0'!=str[i]; i++ ) {
		if( islower( str[i] ) ) {
			str[i] = toupper( str[i] );
		} else if(  isupper( str[i] ) ) {
			str[i] = tolower( str[i] );
		} 
	}
	
	cout<<str<<endl;
	
	return 0;
}

Measured memory_bytes: 1176
//~#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//~#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//~#pragma GCC target("avx2")  //Enable AVX
#include<bits/stdc++.h>
using namespace std;

#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mod=10243;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int mul(int a,int b){
  return ((a)*1ll*(b))%mod;
}

void add(int &a,int b){
  a+=b;
  if(a>=mod)a-=mod;
}

int sub(int a,int b){
  a-=b;
  if(a<0){
    a+=mod;
  }
  return a;
}

int powz(int a,int b){
  int res=1;
  while(b){
    if(b&1){
      res=mul(res,a);
    }
    b/=2;
    a=mul(a,a);
  }
  return res;
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
  input>>x.F>>x.S;
  return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
  for(auto& i:x)
    input>>i;
  return input;
}

template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
  for(auto& i:x)
    output<<i<<' ';
  return output;
}

template<typename T>
vector<pair<T,int>> getvec(int n){
  vector<pair<T,int>>a(n);
  for(int i=0;i<a.size();i++){
    cin>>a[i].F;
    a[i].S=i;
  }
  return a;
}

void clr(auto &a,int n){
  a.clear();
  a.resize(n);
}

void unq(auto &a){
  sort(all(a));
  a.resize(unique(all(a))-a.begin());
}

const int N=200005;

int dp[N][2];
vector<int>adj[N];

void solve(){
	int n,m;
	cin>>n>>m;
	string s;
	cin>>s;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		adj[x].pb(y);
		adj[y].pb(x);
		dp[x][s[y]-'A']++;
		dp[y][s[x]-'A']++;
	}
	queue<int>q;
	vector<int>vis(n);
	for(int i=0;i<n;i++){
		if(min(dp[i][0],dp[i][1])==0){
			vis[i]=1;
			q.push(i);
		}
	}
	while(!q.empty()){
		int tp=q.front();
		q.pop();
		for(auto i:adj[tp]){
			dp[i][s[tp]-'A']--;
			if(dp[i][s[tp]-'A']==0&&vis[i]==0){
				q.push(i);
				vis[i]=1;
			}
		}
	}
	int tot=0;
	for(auto i:vis){
		tot+=i;
	}
	if(tot!=n){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
	
	
	
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc=1;
  //~cin>>tc;
  for(int _=0;_<tc;_++){
    // cout<<"Case #"<<_+1<<": ";
    solve();
    if(_!=tc-1){
      cout<<'\n';
    }
  }
}



Measured memory_bytes: 13136
n,yen = map(int,input().split())
isOK = False
for x in range(yen//10000+1):
    for y in range(yen//5000+1):
        if (n - x - y) >= 0:
            if yen == 10000 * x + 5000 * y + 1000 * (n - x - y):
                isOK = True
                break
    else:
        continue
    break
if isOK:
    print(x,y,n-x-y)
else:
    print(-1,-1,-1)

Measured memory_bytes: 9196
#include <stdio.h>
   
using namespace std;
   
int main(){
    int n,x;
    scanf("%d",&n);
   
    for(int i = 1; i<= n; i++)
    {
        if(i%3 == 0){
            printf(" %d",i);
        }else{
            x = i;
            do{
                if(x%10 == 3){
                    printf(" %d",i);
                    break;
                }
                x /=10;
            }while(x);
        }
    }
    printf("\n");
}


Measured memory_bytes: 2700
import sys
x,k,d = map(int, input().split())


if x < 0:
  x *= -1

if x > k * d:
  print(x-k*d)
  sys.exit()

tmp = x//d
x -= tmp * d
k -= tmp

if k % 2 == 0:
  print(x)
else:
  print((x-d)*-1)


Measured memory_bytes: 9172
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;


int main(){
    
	double a, b, c, d, e, f;
    double x, y;
    
	while(cin>> a>> b>> c >> d>> e>> f){
        
        x = 0.0;
        y = 0.0;
        
                
        y = (c*d-f*a)/(b*d-a*e);
        
        x = (c*e-f*b)/(a*e-b*d);

        if (x == 0) {
            x = 0;
        }
        else if (y == 0) {
            y = 0;
        }
        
        printf("%.3f %.3f\n", x, y);
        
        
	}
    
    
	return 0;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(int i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(int i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(long long N, long long X, std::vector<long long> L){
  vector<ll> sum;
  sum.push_back(0);
  REP(N){
    sum.push_back(sum.back()+L[i]);
  }
  cout<<upper_bound(sum.begin(),sum.end(),X)-sum.begin()<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long X;
    scanf("%lld",&X);
    std::vector<long long> L(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&L[i]);
    }
    solve(N, X, std::move(L));
    return 0;
}


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

  int L[M], R[M];
  rep(i,M) {
    int r,l;
    cin >> l >> r;
    L[i] = l;
    R[i] = r;
  }

  int maxL = 1;
  int minR = N;
  rep(i,M) {
    maxL = max(maxL,L[i]);
    minR = min(minR,R[i]);
}

   int ans = minR - maxL+1;
   ans = max(ans,0);
  cout << ans << endl;
  return 0;
}

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

int main(int argc, const char * argv[]) {
    char s[101], p[101], str[201];
    scanf("%s %s", s, p);
    strcpy(str, s);
    strcat(str, s);
    if(strstr(str, p) == NULL){
        printf("No\n");
    }else{
        printf("Yes\n");
    }
    return 0;
}



Measured memory_bytes: 2112
import heapq

INFTY = 1<<20

N = int(input())
M = [[] for _ in range(N)]
for i in range(N):
    u, k, *adjacents = map(int, input().split())
    for j in range(k):
        edge = adjacents[2*j]
        weight = adjacents[2*j+1]
        M[i].append((weight, edge))

mst = [False for _ in range(N)]
d = [INFTY for _ in range(N)]
d[0] = 0
pq = []
heapq.heappush(pq, (0, 0))

while len(pq) != 0:
    u = heapq.heappop(pq)
    u_edge = u[1]
    u_cost = u[0]

    mst[u_edge] = True

    if d[u_edge] < u_cost:
        continue

    for v in M[u_edge]:
        v_edge = v[1]
        v_cost = v[0]
        if mst[v_edge] == True:
            continue
        if d[u_edge]+v_cost < d[v_edge]:
            d[v_edge] = d[u_edge]+v_cost
            heapq.heappush(pq, (d[v_edge], v_edge))

for i in range(N):
    print("{} {}".format(i, d[i]))


Measured memory_bytes: 68816
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);

std::vector<ll> divisor(ll n) {
	std::vector<ll> res;
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			res.push_back(i);
			if (i != n / i) {
				res.push_back(n / i);
			}
		}
	}
	return res;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	ll n;
	cin >> n;

	ll ans = divisor(n - 1).size() - 1;

	auto div = divisor(n);
	for (auto d : div) {
		if (d == 1) continue;
		ll tmp = n;
		while (tmp % d == 0) {
			tmp /= d;
		}
		if (tmp % d == 1) {
			ans++;
		}
	}

	out(ans);

	return 0;
}

Measured memory_bytes: 3672
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
int s[2010],t[2010];
struct Edge{
	int v,nxt;
}e[4010];int tot=1;
int first[2010],deg[2010];
void build(int u,int v)
{
	e[++tot]=(Edge){v,first[u]};
	first[u]=tot;deg[u]++;
	return ;
}
inline int eid(int x){return x/2;}
int c[2010];
int vis[2010][2010];
bool dfs(int u,int lst,int tar,int id)
{
	if(u==tar)return true;
	for(int i=first[u];i;i=e[i].nxt)
		if(e[i].v!=lst){
			bool flag=dfs(e[i].v,u,tar,id);
			if(flag){
				vis[id][eid(i)]=i&1;
				c[eid(i)]++;
				return true;
			}
		}
	return false;
}
void init()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		build(u,v);
		build(v,u);
	}
	memset(vis,-1,sizeof(vis));
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&s[i],&t[i]);
		dfs(s[i],0,t[i],i);
	}
	int ans=0;
	for(int i=1;i<n;i++)
		ans+=min(c[i],2);
	printf("%d\n",ans);
	return ;
}
int fa[2010],val[2010];
int find(int x)
{
	if(fa[x]==x)return x;
	int f=find(fa[x]);
	val[x]^=val[fa[x]];
	return fa[x]=f;
}
queue<int>q;
bool book[2010];
void work(int u)
{
	book[u]=true;
	for(int i=first[u];i;i=e[i].nxt)
	{
		deg[e[i].v]--;
		if(deg[e[i].v]==1)q.push(e[i].v);
		if(c[eid(i)]>=2)
		{
			int t=eid(i);
			int a=0,b=0;
			for(int o=1;o<=m;o++)
				if(fa[o]==o&&vis[o][t]!=-1)
				{
					if(!a)a=o;
					else{
						b=o;
						break;
					}
				}
			int tmp=vis[a][t]^vis[b][t]^1;
			fa[b]=a;val[b]=tmp;
			for(int i=1;i<n;i++)
				if(vis[b][i]!=-1){
					if(vis[a][i]!=-1)vis[a][i]=-1,c[i]=0;
					else vis[a][i]=vis[b][i]^tmp;
				}
		}
	}
	return ;
}
void solve()
{
	for(int i=1;i<=m;i++)
		fa[i]=i,val[i]=0;
	for(int i=1;i<=n;i++)
		if(deg[i]==1)q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		work(u);
	}
	for(int i=1;i<=m;i++)
	{
		find(i);
		if(val[i])swap(s[i],t[i]);
		printf("%d %d\n",s[i],t[i]);
	}
	return ;
}
int main()
{
	init();
	solve();
	return 0;
}

Measured memory_bytes: 16256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a = 0; int b = 0;
  
  for(int i = 0; i < 10000; i++){
    cin >> a >> b;
    if(a == 0 && b == 0){
      break;
    }
    cout << min(a,b) << " " << max(a,b) << endl;
  }
  
}



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(k,i,n) for(ll i=k;i<n;++i)
#define pb push_back
int main(void){
    ll n,x,m;
    cin>>n>>x>>m;
    vector<ll>id(m+1,-1),s;
    ll c=0;
    while(id[x]==-1){
        id[x]=c++;
        s.pb(x);
        x=x*x%m;
    }
    ll d=c-id[x],ans=0;
    if(n<=d){
        rep(0,i,n)ans+=s[i];
    }else{
        rep(0,i,id[x])ans+=s[i];
        n-=id[x];
        ll sum=0;
        rep(0,i,d)sum+=s[id[x]+i];
        ans+=(n/d)*sum;
        n%=d;
        rep(0,i,n)ans+=s[id[x]+i];
    }
    cout<<ans;
}

Measured memory_bytes: 4700
#include <bits/stdc++.h>
using namespace std;
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
#define ll long long
template <typename T>  ostream& operator<<(ostream& os, const vector<T>& v)  {  os << "[";  for (int i = 0; i < v.size(); ++i) {  os << v[i];  if (i != v.size() - 1)  os << ", ";  }  os << "]";  return os;  }

template<int MOD>
struct ModInt {
  ll x;
  ModInt():x(0){}
  ModInt(ll x):x((x%MOD+MOD)%MOD){}
  int getMod() { return MOD; }
  ModInt operator-() const { return ModInt(0) - *this;}
  ModInt& operator+=(const ModInt& a){ if((x+=a.x)>=MOD) x-=MOD; return *this;}
  ModInt& operator-=(const ModInt& a){ if((x+=MOD-a.x)>=MOD) x-=MOD; return *this;}
  ModInt& operator*=(const ModInt& a){ (x*=a.x)%=MOD; return *this;}
  ModInt operator+(const ModInt& a)const{ return ModInt(*this) += a;}
  ModInt operator-(const ModInt& a)const{ return ModInt(*this) -= a;}
  ModInt operator*(const ModInt& a)const{ return ModInt(*this) *= a;}
  bool operator<(const ModInt& a)const{ return x < a.x;}
  bool operator==(const ModInt& a)const{ return x == a.x;}
  ModInt pow(ll t) const {
    if (!t) return 1;
    ModInt a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  friend ostream & operator << (ostream & out, ModInt<MOD> const & v) {
    out << v.x;
    return out;
  }
};
const int MOD = 1000000007;
using mint = ModInt<MOD>;

template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        int MOD = fact_[0].getMod();
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T perm(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return com(n, k) * fact(k);
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

int main() {
  int n,k; cin >> n >> k;
  vector<ll> A(n);
  loop(i,0,n) cin >> A[i];
  BiCoef<mint> bc(n+1);
  mint ans = 0;
  {
    sort(A.begin(), A.end());
    loop(i,0,n) {
      if (i >= k-1) 
        ans += mint(A[i]) * bc.com(i, k-1);
    }
  }
  {
    reverse(A.begin(), A.end());
    loop(i,0,n) {
      if (i >= k-1) 
        ans -= mint(A[i]) * bc.com(i, k-1);
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main()
{
    array<int, 9> As;
    copy_n(istream_iterator<int>(cin), 9, As.begin());

    int N;
    cin >> N;

    std::vector<int> bs;
    copy_n(istream_iterator<int>(cin), N, back_inserter(bs));

    const int MARK = 99999;
    for (int b : bs)
    {
        auto it = find(As.begin(), As.end(), b);
        if (it != As.end())
        {
            *it = MARK;
        }
    }

    if ((As[0] == MARK && As[1] == MARK && As[2] == MARK) ||
        (As[3] == MARK && As[4] == MARK && As[5] == MARK) ||
        (As[6] == MARK && As[7] == MARK && As[8] == MARK) ||
        (As[0] == MARK && As[3] == MARK && As[6] == MARK) ||
        (As[1] == MARK && As[4] == MARK && As[7] == MARK) ||
        (As[2] == MARK && As[5] == MARK && As[8] == MARK) ||
        (As[0] == MARK && As[4] == MARK && As[8] == MARK) ||
        (As[2] == MARK && As[4] == MARK && As[6] == MARK))
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }

    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
typedef long long ll;

bool calc(int a, int b, int c) {
  return a == b && b != c;
}

int main(void) {
  int n;
  cin >> n;
  bool ok = true;
  REP(i, n) {
    int v;
    cin >> v;
    if(v % 2 == 0 && (v % 3 != 0 && v % 5 != 0)) {
      ok = false;
    }
  }
  if(ok) {
    puts("APPROVED");
  } else {
    puts("DENIED");
  }
  return 0;
}


Measured memory_bytes: 256
from itertools import product, chain
from collections import deque


def solver1(a, b, c, k):
    apb_sorted = sorted([a + b for a, b in product(a, b)])[-k:]
    ans_list = sorted(
        list(chain.from_iterable([[_c + ab for ab in apb_sorted] for _c in c[:k]]))
    )
    it = reversed(ans_list)
    for _ in range(k):
        print(next(it))


def solver2(a, b, c, k):
    n = len(a)
    m = min(k, n)
    pqr = deque()
    for p in range(m):
        for q in range(m):
            for r in range(m):
                if (p + 1) * (q + 1) * (r + 1) > k:
                    break
                else:
                    pqr.append(a[-p - 1] + b[-q - 1] + c[-r - 1])
    it = reversed(sorted(pqr))
    for _ in range(k):
        print(next(it))


if __name__ == "__main__":
    x, y, z, k = list(map(int, input().split(" ")))
    a = sorted(list(map(int, input().split(" "))))
    b = sorted(list(map(int, input().split(" "))))
    c = sorted(list(map(int, input().split(" "))))
    solver2(a, b, c, k)


Measured memory_bytes: 9888
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    s = list(input())

    # 1番目と2番目を決め打ち
    # SS，SW，WW，WS
    # 1文字目とn + 1文字目が一致するかどうか
    for pair in ['SS', 'SW', 'WW', 'WS']:
        ans = ['' for _ in range(n + 1)]

        for index, p in enumerate(pair):
            ans[index] = p

            for j in range(1, n):
                if s[j] == 'o':
                    if ans[j] == 'S':
                        ans[j + 1] = ans[j - 1]
                    else:
                        if ans[j - 1] == 'S':
                            ans[j + 1] = 'W'
                        else:
                            ans[j + 1] = 'S'
                else:
                    if ans[j] == 'S':
                        if ans[j - 1] == 'S':
                            ans[j + 1] = 'W'
                        else:
                            ans[j + 1] = 'S'
                    else:
                        ans[j + 1] = ans[j - 1]

        if ans[0] == ans[-1]:
            # 気がつけなかった点
            # 2文字目とN文字目が矛盾していないかチェック
            if ans[n - 1] == ans[1] and ((s[0] == 'o' and ans[0] == 'S') or (s[0] == 'x' and ans[0] == 'W')):
                print(''.join(ans[:-1]))
                break
            elif ans[n - 1] != ans[1] and ((s[0] == 'o' and ans[0] == 'W') or (s[0] == 'x' and ans[0] == 'S')):
                print(''.join(ans[:-1]))
                break
    else:
        print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 5680
#include<stdio.h>
int main(void){
	int a,b,c,d,e,f,g;
	while(1){
		scanf("%d %d",&a,&b);
		c=a;
		d=b;
		if(a==0&b==0){
			goto hata;
		}else{
			for(e=1;e<=c;e++){
				for(f=1;f<=d;f++){
					g = (e+f) % 2;
					if(g==0){
						putchar('#');
					}else if(g==1){
						putchar('.');
					}
				}putchar('\n');
			}putchar('\n');
		}
	}
	hata:
	return 0;
}

Measured memory_bytes: 572
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include<numeric>
using namespace std;
using P = pair<int, int>;
#define rep(i,n) for(int i=0; i<(n);i++)
typedef long long ll;


int main(){
    int n, m; cin >> n >> m;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    sort(a.rbegin(), a.rend());
    double sum = 0;
    rep(i,n) sum += a[i];
    bool ans = true;
    rep(i,m){
        double l = (double)a[i]/sum;
        double r = (double)(1.0/(4*m));
        if(l < r){
            ans = false;
            break;
        }
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 888
# https://atcoder.jp/contests/tenka1-2017/tasks/tenka1_2017_c
# 式をこねくり回せ

N = int(input())

from itertools import product

for n, h in product(range(1, 3501), range(1, 3501)):
    bunbo = (4 * n * h - N * n - N * h)
    if bunbo <= 0:
        continue
    w = (N * h * n) / bunbo
    if w.is_integer():
        print(n, h, int(w))
        exit()


Measured memory_bytes: 40924
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);

    int MOD = (int)998244353;

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        char s = sc.next().charAt(0);
        char t = sc.next().charAt(0);

        if (s == t) {
            System.out.println("=");
        } else if (s < t) {
            System.out.println("<");
        } else {
            System.out.println(">");
        }

    }
}



Measured memory_bytes: 21716
# your code goes here
N=int(input())
a=[int(i) for i in input (). split ()]
M=0
M1=0
for i in range (N):
    if a[i]%2==0:
        M+=1
        a[i]//=2
        if a[i]%2==0:
            M1+=1
N-=M
if N==0:
    p="Yes"
elif M1>=N:
    p="Yes"
elif M==M1 and M1+1>=N:
    p="Yes"
else:
    p="No"
print (p)

Measured memory_bytes: 14252
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define maxn 100005
#define INF (LL)1e16
using namespace std;
int n,m,t,x[maxn];
LL dp[maxn];
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;i++) scanf("%d",&x[i]);
	sort(x+1,x+n+1);
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	LL mn=INF; int now=0;
	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1]+t+x[i]-x[i-1];
		while(2*(x[i]-x[now+1])>=t)
		{
			mn=min(mn,dp[now]-2ll*x[now+1]);
			now++;
		}
		dp[i]=min(2*x[i]+mn,dp[now]+t);
	}
	printf("%lld\n",dp[n]+m);
}

Measured memory_bytes: 1280