akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using std::map;
using std::set;
using std::bitset;
using std::vector;
using std::string;
using std::multimap;
using std::multiset;
using std::deque;
using std::queue;
using std::stack;
using std::pair;
using std::iterator;

using std::sort;
using std::stable_sort;
using std::reverse;
using std::max_element;
using std::min_element;
using std::unique;
using std::ios_base;
using std::swap;
using std::fill;

using std::setprecision;
using std::fixed;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef string S;

namespace MySpace{

};

#define F(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define fi first
#define se second
#define re return
#define all(x) (x).begin(), (x).end()

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

long long max(long long a, long long b)
{
    if (a > b) return a;
    return b;
}

long long min(long long a, long long b)
{
    if (a < b) return a;
    return b;
}

int n;
int a[500000];
map<int, int> mm;

signed main()
{
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        mm[a[i]] = i;
    }
    sort(a, a + n);
    int q = 0;
    for (int i = 0; i < n; i++)
    {
        if (mm[a[i]] % 2 != i % 2)
        {
            q++;
        }
    }
    cout << q / 2;
}


Measured memory_bytes: 5376
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

vector<int> cost;
vector<vector<int>> edge;
vector<bool> isVisited;

void dfs(int node, vector<int>& w)
{
    isVisited[node] = true;
    w.push_back(cost[node]);

    for (int ch : edge[node]) {
        if (!isVisited[ch]) {
            dfs(ch, w);
        }
    }
}

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

    cost.resize(n);
    rep(i, n)
    {
        cin >> cost[i];
    }

    edge.resize(n);
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    int c = 0;
    int64_t result = 0;
    isVisited.resize(n, false);

    vector<int> cand;
    rep(i, n)
    {
        if (!isVisited[i]) {
            c++;
            vector<int> w;
            dfs(i, w);

            sort(w.begin(), w.end());
            result += w[0];
            copy(w.begin() + 1, w.end(), back_inserter(cand));
        }
    }

    if (n < 2 * (c - 1)) {
        cout << "Impossible" << endl;
        return 0;
    }

    if (c == 1) {
        cout << 0 << endl;
        return 0;
    }
    int a = 2 * (c - 1) - c;
    sort(cand.begin(), cand.end());
    rep(i, a)
    {
        result += cand[i];
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 7292
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <algorithm>
using namespace std;


int main()
{
	string str;
	cin >> str;

	for(int i=0;i<4;i++){
		int cnt = 0;
		for(int j=0;j<4;j++){
			if(str[i] == str[j])
				cnt++;
		}
		if(cnt != 2){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

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

int main() {
  int64_t N;
  cin >> N;
  
  vector<int64_t> A(N);
  vector<int64_t> B(N+1);
  for( int64_t i = 0; i < N; i++ ){
    cin >> A.at(i);
    B.at(i+1) = B.at(i) + A.at(i);
  }
  
  sort(B.begin(), B.end());
  
  int64_t ans = 0;
  int64_t count = 1;
  for( int64_t i = 0; i < N; i++ ){
    if( B.at(i) == B.at(i+1) ){
      count++;
    }else if( B.at(i) != B.at(i+1) && count > 1 ){
      ans += count * (count-1) / 2;
      count = 1;
    }
  }
  if( count > 1 ){
    ans += count * (count-1) / 2;
  }
  cout << ans << endl;
}


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

int main(){
	int S;
	cin>>S;
	cout<<S/3600<<":"<<S/60%60<<":"<<S%60<<endl;
}
/*for(初期化式;条件式;終了のときの式)
  for(int i=a;i<=b;i++){
     cout<<i<<endl;
  }*/



Measured memory_bytes: 3112
#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
use std::collections::VecDeque;

fn main() {
    let stdin = std::io::stdin();
    let mut sc = Scanner { reader: stdin };

    let h: usize = sc.read();
    let w: usize = sc.read();

    let mut ss = vec![];
    for _ in 0..h {
        ss.push(sc.chars());
    }

    let mut costs = vec![vec![-1i64; w]; h];
    costs[0][0] = 0;

    let mut q: VecDeque<(i64, i64, i64)> = VecDeque::new();
    q.push_back((0, 0, 1));
    while q.len() >= 1 {
        let (x, y, c) = q.pop_front().unwrap();
        let n_cost = c + 1;
        for &(dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)].iter() {
            let nx = x + dx;
            let ny = y + dy;
            if nx < 0 || nx >= h as i64 { continue };
            if ny < 0 || ny >= w as i64 { continue };

            let nx = nx as usize;
            let ny = ny as usize;
            if ss[nx][ny] == '#' { continue };

            if n_cost >= costs[nx][ny] && costs[nx][ny] != -1 {
                continue;
            }
            costs[nx][ny] = n_cost;
            q.push_back((nx as i64, ny as i64, n_cost));
        }
    }

    let cost = costs[h-1][w-1];
    let mut cnt = 0;
    for row in ss {
        for c in row {
            if c == '.' {
                cnt += 1;
            }
        }
    }
    if cost == -1 {
        println!("{}", -1);
    } else {
        println!("{}", cnt-cost);
    }
}


pub struct Scanner<R> {
    reader: R,
}
impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

Measured memory_bytes: 4352
#include<stdio.h>

int search(int A[],int n,int key){
	int i = 0;
	A[n] = key;
	while(A[i] != key)i++;
	return i != n;
}

int main(){
	int i, n, A[10000+1], q, key, sum=0;
	
	scanf("%d",&n);
	for(i=0; i<n; i++)scanf("%d",&A[i]);
	
	scanf("%d",&q);
	for(i=0; i<q; i++){
		scanf("%d", &key);
		if(search(A, n, key))sum++;
	}
	printf("%d\n", sum);
	
	return 0;
}
		

Measured memory_bytes: 640
def sub(x):
	global A;	global F;	global K
	s = 0
	for i in range(N):
		s += max(A[i] - x // F[i], 0)
	return s <= K

N, K = map(int,input().split())
A = list(map(int,input().split())); A.sort()
F = list(map(int,input().split())); F.sort(); F.reverse()
# print(A); print(F)

l = -1; r = max(A) * max(F)
while r - l > 1:
	m = (l + r) // 2
	if sub(m):
		r = m
	else:
		l = m

print(r)

Measured memory_bytes: 119628
# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion
class union_find:
    def __init__(self, n):
        self.n = n
        self.rank = [0]*n
        self.parent = [int(j) for j in range(n)]
    
    def union(self,i,j):
        i = self.find(i)
        j = self.find(j)
        if self.rank[i] == self.rank[j]:
            self.parent[i] = j
            self.rank[j] += 1

        elif self.rank[i] > self.rank[j]:
            self.parent[j] = i
        else:
            self.parent[i] = j

    def find(self, i):
        temp = i
        if self.parent[temp] != temp:
            self.parent[temp] = self.find(self.parent[temp])
        return self.parent[temp]
from math import log2, ceil
from collections import deque, Counter as CC
def main():
# Enter your code here. Read input from STDIN. Print output to STDOUT
    # for t in range(int(input())):
        
        n = input()
        ans = 0
        for i in range(len(n)):
            ans+=int(n[i])
        if(ans%9!=0):
            print("No")
        else:
            print("Yes")
        # n,x,t = [int(j) for j in input().split()]
# )
        # l = [int(j) for j in input().split()]




        # b = [int(j) for j in input().split()]

            # s = n-1

        # s = input()




        # a = list(a)
        # print(a)
        # for i in a:



        



if __name__ == "__main__":
    main()

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

ll N, Q;
vector<char> vch;
set<ll> S[26];

signed main(){
    cin >> N;
    vch.resize(N);
    for(int i=0;i<N;i++) {
        cin >> vch[i];
        S[vch[i]-'a'].insert(i);
    }
    /*
    for(int i=0;i<26;i++) {
        for(set<ll>::iterator it=S[i].begin();it!=S[i].end();it++) {
            cout << i << " " << *it << endl;
        }
    }
    */
    cin >> Q;
    for(int i=0;i<Q;i++) {
        int q;
        cin >> q;
        if(q==1) {
            int id;
            char c;
            cin >> id >> c;
            id--;
            S[vch[id]-'a'].erase(id);
            vch[id]=c;
            S[vch[id]-'a'].insert(id);
        }
        else {
            int l, r, ans=0;
            cin >> l >> r;
            l--;
            r--;
            for(int i=0;i<26;i++) {
                if(S[i].empty()||S[i].lower_bound(l)==S[i].end()) continue;
                //for(set<ll>::iterator it=S[i].begin();it!=S[i].end();it++) {
                    //cout << i << " " << *it << " " << *S[i].lower_bound(l) << endl;
                //}
                if(*S[i].lower_bound(l)<=r) {
                    ans++;
                    //cout << i << " " << l << " " << *S[i].lower_bound(l) << " "  << r << endl;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 24192
x,n = map(int, input().split())
p = list(map(int, input().split()))
s = set(p)
from collections import defaultdict
d = defaultdict(list)
for i in range(-100, 210):
    if i not in s:
        j = abs(i-x)
        d[j].append(i)
k = min(d.keys())
ans = min(d[k])
print(ans)


Measured memory_bytes: 64896
#[allow(unused_imports)]
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
   input! {
      x: [usize; 5]
   }
   for i in 0..5 {
      if x[i] == 0 {
         println!("{}", i+1);
      }
   }
}


Measured memory_bytes: 2080
//=================================
// Created on: 2018/09/19 14:38:21
//=================================
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 10000010;
bool is_prime[MAXN + 10];
int main()
{
    fill(is_prime, is_prime + MAXN + 10, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= MAXN; i++) {
        if (is_prime[i] == true) {
            for (int k = 2 * i; k <= MAXN; k += i) {
                is_prime[k] = false;
            }
        }
    }

    int N, ans = 0;
    cin >> N;
    for (int k = 3; k <= N; k++) {
        if (is_prime[k] and is_prime[k + 2]) ans += 2;
    }
    cout << ans << endl;
}



Measured memory_bytes: 12864
from heapq import *

# Aの中でxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aのリストでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    # 根をbxに統一
    A[bx] = bx
    A[by] = bx

N = int(input())
X = [(0,0)] * N
Y = [(0,0)] * N
E = [(0,0)] * N

for i in range(N):
    x, y = map(int, input().split())
    X[i] = (x, i)
    Y[i] = (y, i)
    E[i] = (x, y)

X.sort()
Y.sort()
H = []
heapify(H)

for i in range(N - 1):
    x1, j1 = X[i]
    x2, j2 = X[i + 1]
    y1, k1 = Y[i]
    y2, k2 = Y[i + 1]
    # ヒープ構造を用いて常にHの最初に最小値を持ってくる
    # X座標とY座標でそれぞれHに追加
    heappush(H, (x2 - x1, j1, j2))
    heappush(H, (y2 - y1, k1, k2))

answer = 0
V = [i for i in range(N)]

while H:
    w, s, t = heappop(H)
    # sとtの集合が異なっていた時、道を作る
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w

print(answer)


Measured memory_bytes: 61092
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int n, x, freq[105], ans;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (!freq[x]) {
			ans++;
		}
		freq[x] = 1;
	}
	cout << ans;
	system("pause");
}

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

typedef long long ll;
ll n,x,ans,x1,x2;

int main(){
	scanf("%lld%lld",&n,&x);
	ans=n;
	x1=x,x2=n-x;
	while(1){
		if(x1<x2) swap(x1,x2);
		if(!x2) break;
		if(x1%x2==0) ans-=x2;
		ans+=x2*(x1/x2)*2;
		x1-=x2*(x1/x2);
	}
	printf("%lld\n",ans);
	return 0;
} 

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

#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const ll MOD = 1000000007;
static const ll MAX = 10000;
static const ll INFTY = 1e18;

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;
// 入力
// int H, W;
vector<vector<char>> field;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// 深さ優先探索
vector<bool> seen;
vector<int> colors;


vector<double>  w, p;
vector<double>  q;

long long fac[MAX], finv[MAX], inv[MAX];


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


ll test_pow4(ll _x, ll _n)
{
	ll ret = 1;
	while(0 < _n)
	{
		if((_n % 2) == 0)
		{
			_x *= _x;
      _x %= MOD;
			_n >>= 1;
		}
		else
		{
			ret *= _x;
      ret %= MOD;
			--_n;
		}
	}
  // cout << n << " " << x << endl;
	return ret;
}
  



ll nCr(ll n, ll r){
    ll ans;
    ll bunsi = 1;
    ll bunbo = 1;
 
    if(n / 2 < r) r = n - r;
    for(ll i = n; i > n - r; i--){
        bunsi *= i;
        bunsi %= MOD;
    }
    for(ll i = 1; i <= r; i++){
        bunbo *= i;
        bunbo %= MOD;
    }
    bunbo = modinv(bunbo, MOD);

    // cout << bunbo << endl;

    ans = bunsi * bunbo;
 
    return ans;
}


int main() {

  ll n, a, b;
  ll ans = 0;
  cin >> n >> a >> b;

  ll _a = nCr(n, a); _a %= MOD;
  ll _b = nCr(n, b); _b %= MOD;

  ans = (test_pow4(2, n) - 1 - _a - _b) % MOD;
  if(ans < 0)ans += MOD;

  cout << ans << endl;

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

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

using namespace std;

//#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF (1 << 30)
#define fi first
#define se second

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }


signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    char a, b;
    cin >> a >> b;
    if(a > b) cout << ">" << endl;
    else if(a < b) cout << "<" << endl;
    else cout << "=" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

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

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

vector<ll> d(100001,-INF);
vector< vector<ll> > G(100001,vector<ll>(0));

ll dp(ll i){
  if(d[i] != -INF) return d[i];
  else if( G[i].size() == 0 ) return 0;
  else{
    ll G_max=-INF;
    for(auto e:G[i]){
      G_max=max(G_max,dp(e));
    }
    d[i]=G_max+1;
    return d[i];
  }
}

int main(void){

  ll n,m;
  cin>>n>>m;
  vector<ll> x(m);
  vector<ll> y(m);


  rep(i,m){
    cin>>x[i];
    cin>>y[i];
    G[x[i]].pb(y[i]);
  }
  /*
  for(auto g:G){
    for(auto gg:g){
      cout << gg << " ";
    }
    cout << endl;
  }
  */
  rep1(i,n){
    dp(i);
  }

  cout << *max_element(all(d)) << endl;

  return 0;

}


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

using ll = long long;
using ull = unsigned long long;

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

void solve() {
	int n, w;
	cin >> n >> w;
	vector<ll> wt(n), v(n);
	for(int i = 0; i < n; ++i) {
		cin >> wt[i] >> v[i];
	}
	vector<vector<ll> > dp(2, vector<ll>(w + 1));
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= w; j++) {
			if(i == 0 || j == 0) {
				dp[i % 2][j] = 0;
				continue;
			}
			dp[i % 2][j] = max(dp[(i - 1) % 2][j], (j >= wt[i - 1] ? v[i - 1] + dp[(i - 1) % 2][j - wt[i - 1]] : 0));
		}
	}
	cout << dp[n % 2][w] << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	solve();
	
	return 0;
}


Measured memory_bytes: 5576
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a;i<n;i++)
#define ve vector
#define ss second 
#define ff first
#define pf pop_front
#define pob pop_back
#define psf push_front
#define res(x) cout<<x<<'\n'
#define read(t) ll t;cin>>t

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    int a,b;
    cin>>a>>b;
    cout<<6-a-b<<endl;
    
    


   

}

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

using namespace std;

#define INF 1000000007;

int n,k;
int dp[100000];
int h[100000];

int dfs(int a){
  if(a == n) return 0;
  for(int i = 1; i <= k && i+a < n; i++){
    dp[i+a] = min( dp[i+a], dp[a] + abs(h[i+a] - h[a]));
  }
  return dfs(a+1);
}

int main(){
  cin >> n >> k;
  for(int i = 0; i < n ; i++){
    cin >> h[i];
  }
  for(int i = 0; i < n; i++){
    dp[i] = INF;
  }
  dp[0] = 0;
  dfs(0);
  cout << dp[n-1] << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
long long COM(int n, int k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  COMinit();
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) {
    cin >> a[i];
  }

  sorti(a);
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    ans += a[i] * (COM(i, k-1) - COM(n-1-i, k-1));
    ans %= mod;
  }

  cout << ans << endl;
}

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


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

	int A[100];
	for(int i=0; i<M; i++){
		cin >> A[i];
	}
	
	int C[100] = {};
	for(int j=0; j<M; j++){
		int B[100];
		int X = 0;
		for(int l=0; l<N; l++){
			cin >> B[l];
			if(A[j] == B[l]){
				C[l]++;
			}
			else if(A[j] != B[l]){
				X += 1;
			}
		}
		C[A[j]-1] += X;
		
	}

	for(int k=0; k<N; k++){
		cout << C[k] << endl;
	}
}




Measured memory_bytes: 3100
#![allow(unused_imports)]
use itertools::Itertools;
use proconio::{input, marker::*};
use std::cmp::*;
use std::collections::*;
use superslice::*;

fn main() {
    input! {
        n: usize
    }

    let mut v: Vec<usize> = vec![0; n + 1];

    for i in 1..=n {
        let mut j = i;
        while j <= n {
            v[j] += 1;
            j += i;
        }
    }

    let mut ans = 0;
    for i in 1..=n {
        ans += i * v[i];
    }

    println!("{}", ans);
}


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

int main(){
	string label;
	int joiCount = 0;
	int ioiCount = 0;
	int joiIndex = 0;
	int ioiIndex = 0;
	while(true){
		cin >> label;
		if(cin.eof()){
			break;
		}
		joiCount = 0;
		ioiCount = 0;
		joiIndex = 0;
		ioiIndex = 0;
		
		while(label.find("JOI", joiIndex) != string::npos){
			joiIndex = label.find("JOI", joiIndex) + 1;
			joiCount++;
		}
		
		while(label.find("IOI", ioiIndex) != string::npos){
			ioiIndex = label.find("IOI", ioiIndex) + 1;
			ioiCount++;
		}
		
		cout << joiCount << '\n' << ioiCount << '\n';
	}
	return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, cc;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 105;
int a[maxn], b[maxn], c[maxn], d[maxn];
ll dis[55][5500];
typedef pair<int, int> pi;
vector<pi> G[maxn];

void dij(){
	memset(dis,0x3f,sizeof(dis));
    dis[1][cc] = 0;
    priority_queue<pair<ll, pi>, vector<pair<ll, pi> >, greater<pair<ll, pi> > > pq;
    pq.emplace(0, make_pair(1, cc));
    while(!pq.empty()){
        auto p = pq.top(); pq.pop();
        ll D = p.first;
        int u = p.second.first;
        int coins = p.second.second;
        int coins1 = min(coins + c[u], 5000);
        if(dis[u][coins] + d[u] < dis[u][coins1]){
            dis[u][coins1] = dis[u][coins] + d[u];
            pq.emplace(dis[u][coins1], make_pair(u, coins1));
        }
        for(auto edge : G[u]){
            int v = edge.first;
            int id = edge.second;
            if(coins >= a[id] && dis[v][coins - a[id]] > dis[u][coins] + b[id]){
                dis[v][coins - a[id]] = dis[u][coins] + b[id];
                pq.emplace(dis[v][coins - a[id]], make_pair(v, coins - a[id]));
            }
        }
    }
    for(int i = 2;i <= n;i++){
        ll ans = inf;
        for(int j = 0;j <= 5000;j++){
            ans = min(ans, dis[i][j]);
        }
        cout << ans << endl;
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> cc;
    cc = min(cc, 5000);
    for(int i = 1;i <= m;i++){
        int u, v;
        cin >> u >> v >> a[i] >> b[i];
        G[u].push_back({v, i});
        G[v].push_back({u, i});
    } 
    for(int i = 1;i <= n;i++){
        cin >> c[i] >> d[i];
    }
    dij();
    return 0;
}

Measured memory_bytes: 9764
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <iostream>
#include <ctype.h>
#include <string>
typedef long long ll;
using namespace std;

int main(){
  int n,m;
  cin>>n;
  string st;
  cin>>st;
  if(n>=3200) cout <<st;
  else cout<<"red";
}

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

int func(int A, int B, int C) {
  if (A % 2 == 1 || B % 2 == 1 || C % 2 == 1) return 0;
  if (A == B && A == C) return -1;
  return func((B + C) / 2, (A + C) / 2, (A + B) / 2) + 1;
}

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

  int ans = func(A, B, C);
  cout << ans << endl;
}

Measured memory_bytes: 256
def cross(vT,AT):
   return [sum([x*y for x,y in zip(vT,a)]) for a in AT]

me=1.0/6
while True:
    [n,t,l,b] = [int(x) for x in raw_input().split()]
    if n|t|l|b == 0:break
    ls={}
    for i in xrange(l):
        ls[int(raw_input())]=n+i+1
    bs=[]
    for i in xrange(b):
        bs.append(int(raw_input()))
    AT=[]
    for i in xrange(n+l+1):
        AT.append([0.0]*(n+l+1))
    for i in xrange(n):
        for j in xrange(1,7):
            x=i+j
            if x>n:x=n*2-x
            if x in ls:
                AT[ls[x]][i]+=me
            elif x in bs:
                AT[0][i]+=me
            else:
                AT[x][i]+=me
    AT[n][n]=1.0
    for k,v in ls.iteritems():
        AT[k][v]+=1.0
    bT=[0.0]*(n+l+1)
    bT[0]=1.0
    for i in xrange(t):
        bT=cross(bT,AT)
    print '%.6f' % bT[n]

Measured memory_bytes: 4536
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
    string cmpS = "abcdefghijklmnopqrstuvwxyz";
    string S;
	cin >> S;
    int res = 0;
    sort(S.begin(), S.end());
    for (int i = 0; i < cmpS.size(); i++) {
        res = S.find(cmpS[i]);
        if (res == string::npos) {
            cout << cmpS[i] << endl;
            return 0;
        }
    }
    cout << "None" << endl;
	return 0;
}

Measured memory_bytes: 764
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
        int h = sc.nextInt();
        int w = sc.nextInt();
        if(h == 0 && w ==0) break;
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    if(i == 0 || j == 0 || w-1 == j || h-1 == i) System.out.print("#");
                    else System.out.print(".");
                }
                System.out.println();
            }
        System.out.println();
        }
    }
}


Measured memory_bytes: 36772
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner stdIn=new Scanner(System.in);
		int a[]=new int[3],i,j,t;
		for(i=0;i<3;i++) a[i]=stdIn.nextInt();
		for(i=0;i<2;i++) {
			for(j=2;j>i;j--) {
				if(a[j-1]>a[j]) {
					t=a[j-1];
					a[j-1]=a[j];
					a[j]=t;
				}
			}
		}
		System.out.print(a[2]-a[1]+a[1]-a[0]);
	}
}

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

public class Main {

    static long rec(int i, int j, long[] b, long[][] dp) {
        if (dp[i][j] != Long.MAX_VALUE) {
            return dp[i][j];
        }

        if (j - i == 1) {
            return dp[i][j] = 0;
        }

        for (int k = 1; k < (j - i); k++) {
            dp[i][j] = Math.min(dp[i][j], rec(i, i + k, b, dp) + rec(i + k, j, b, dp));
        }

        return dp[i][j] = dp[i][j] + b[j] - b[i];
    }

    public static void main(String[] args) {
        Scanner std = new Scanner(System.in);
        int n = std.nextInt();
        int[] a = new int[n];
        long[] b = new long[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = std.nextInt();
        }

        for (int i = 0; i < n; i++) {
            b[i + 1] = a[i] + b[i];
        }

        long[][] dp = new long[n+1][n+1];
        for (int i = 0; i < n+1; i++) {
            Arrays.fill(dp[i], Long.MAX_VALUE);
        }

        long res = rec(0, n, b, dp);
        System.out.println(res);
    }
}


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

int main() {
    string S;
    cin >> S;
    for (int i = 0; S[i];i++){
        S[i] = char('x');
    }
  cout << S << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long N;
  long long K;
  cin>>N>>K;
  if(K==N+1){
    cout<<1<<endl;
  }
  else{
    long long sum=0;
    for(int i=K;i<N+2;i++){
      sum=sum+i*(N-i+1)+1;
    }
    cout<<sum%1000000007<<endl;
  }
}

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

int main()
{
  char S[6];
  for(int i=0 ; i<6 ; i++)
    cin>>S[i];

  if(S[2] == S[3] && S[4] == S[5])
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;

    return 0;
}


Measured memory_bytes: 256
N, M, X, Y = gets.chomp.split.map(&:to_i)
x = gets.chomp.split.map(&:to_i).sort
y = gets.chomp.split.map(&:to_i).sort

l = x[-1] + 1
r = y[0]

if ((l..r).to_a & (X+1..Y).to_a).size > 0
  puts 'No War'
else
  puts 'War'
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int number[3], tmp;
  for(int n = 0; n < 3; n++){
    cin >> number[n];
  }
  for (int i=0; i<3; ++i) {
    for (int j=0; j<3; ++j) {
      if (number[i] > number[j]) {
        tmp =  number[i];
        number[i] = number[j];
        number[j] = tmp;
      }
    }
  }
  if(number[0] == 7 && number[1] == 5 && number[2] == 5){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <cstring>
using namespace std;
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
using namespace std;
ll a[101][3],dp[101][100009];
int n,w;
ll f(int item,int wight){
    if (item==n+1)
        return 0;
    if (wight<a[item][1])
        return f(item+1,wight);
    if (dp[item][wight]!=-1)
        return dp[item][wight];
    return dp[item][wight]=max(a[item][2]+f(item+1,wight-a[item][1]),f(item+1,wight));
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>n>>w;
    for (int i=1;i<=n;i++)
        cin>>a[i][1]>>a[i][2];
    memset(dp,-1,sizeof dp);
    cout<<f(1,w)<<endl;
    return 0;
}


Measured memory_bytes: 79232
import sys
max_int = 1000000001  # 10^9+1
min_int = -max_int

h1, m1, h2, m2, k = map(int, sys.stdin.readline().split())

diff = (h2 - h1) * 60 + m2 - m1
if diff < 0:
    diff += 60 * 24

print(max(diff - k, 0))



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

int main(void) {
  char s[201];
  while (scanf("%s", s), strcmp(s, "-")) {
    int m;
    scanf("%d", &m);

    int idx=0, i;
    for (i=0; i<m; i++) {
      int h;
      scanf("%d", &h);
      idx+=h;
    }

    int len=strlen(s);
    idx%=len;

    printf("%s%.*s\n", &s[idx], idx, s);
  }
}


Measured memory_bytes: 2048
#!/usr/bin/env python3

N = int(input())
# S = input()
# N, K = map(int, input().split())
# A = list(map(int, input().split()))
from collections import Counter

def main():
    A = [int(input()) for _ in range(N)]
    cnt = Counter(A).items()
    ans = 0
    for k, v in cnt:
        if v % 2 == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 16620
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;


int main() {
	int n; ll m; cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	int lo = 0, hi = 2e5 + 1;
	while (hi - lo > 1) {
		int mid = lo + (hi - lo) / 2;
		ll cnt = 0;
		for (int i = 0; i < n; i++) {
			int targ = mid - a[i];
			auto iter = lower_bound(a.begin(), a.end(), targ);
			cnt += a.end() - iter;
		}
		if (cnt < m) hi = mid;
		else lo = mid;
	}

	vector<ll> sum(n + 1);
	for (int i = n - 1; i >= 0; i--) {
		sum[i] += sum[i + 1] + a[i];
	}
	ll cnt = 0, s = 0;
	for (int i = 0; i < n; i++) {
		int targ = lo - a[i];
		auto iter = lower_bound(a.begin(), a.end(), targ);
		ll c = a.end() - iter;
		cnt += c;
		int t = iter - a.begin();
		s += sum[t] + c*a[i];
	}
	cout << s - (cnt - m)*lo << endl;
	return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)

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

	ll sum = 0;
	ll t = N;
	while (t > 0) {
		sum += t % 10;
		t /= 10;
	}
	cout << ((N % sum == 0) ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
#define md 998244353
#define INF LLONG_MAX
#define F first
#define S second
#define sz(x) (long long)x.size()
#define vi vector<int>
#define vll vector<long long>
#define vpl vector<pair<long long,long long> >
#define vpi vector<pair<int,int> >
#define pb push_back
#define debug(x) cerr<<#x<<"= "<<x<<endl
#define all(v) v.begin(),v.end()
#define TT ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define endl '\n'
#define MAXN 200005
typedef long long ll;
typedef long double ld;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll n;
    cin>>n;
    vll a(n);
    ll sum=0;
    map<ll,ll> mp;
    rep(i,0,n){
        cin>>a[i];
        mp[a[i]]++;
    }
    for(auto e:mp){
        sum+=e.S*(e.S-1)/2;
    }
    rep(i,0,n){
        ll cnt=mp[a[i]];
        ll temp=sum-(cnt*(cnt-1)/2)+((cnt-1)*(cnt-2)/2);
        cout<<temp<<endl;

    }

    return 0;
}

Measured memory_bytes: 11136
import java.util.*;

//update 2020/1/1 23:01

public class Main{

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

  public static void main(String[] args) {

    int h1 = nextInt();
    int m1 = nextInt();
    int h2 = nextInt();
    int m2 = nextInt();
    int k = nextInt();

    int up = 60*h1 + m1;
    int down = 60*h2 + m2;

    int limit = down - k;



    System.out.println(limit-up);

  }

  static int lcm(int a,int b){
    return a*b*gcd(a,b);
  }

  static int gcd(int a,int b){
    if(a%b!=0){
      return gcd(b,a%b);
    }
    else{
      return b;
    }
  }

  /*
    static String toSmall(String s){
      char c = s.charAt(0);
      //if(Character.isUpperCase(c)){
      if(c<=90){
        c += 32;
      }
      return String.valueOf(c);
    }
    static String toBig(String s){
      char c = s.charAt(0);
      //if(Character.isLowerCase(c)){
      if(c>=97){
        c -= 32;
      }
      return String.valueOf(c);
    }
  */

  static String toSmall(String s){
    return s.toLowerCase();
  }

  static String toBig(String s){
    return s.toUpperCase();
  }

  static String next(){
    return sc.next();
  }

  static int nextInt(){
    return Integer.parseInt(sc.next());
  }

  static long nextLong(){
    return Long.parseLong(sc.next());
  }

  static double nextDouble(){
    return Double.parseDouble(sc.next());
  }

  static String[] splitString(String s){
    return s.split("");
  }

  static char[] splitChar(String s){
    return s.toCharArray();
  }

  static int charToInt(char a){
    return a - 48;
  }

////////////////////////////////////////////
  public static int max(int[] a){
    int lng = a.length;
    int max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
  public static long max(long[] a){
    int lng = a.length;
    long max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
////////////////////////////////////////////

////////////////////////////////////////////
  public static int min(int[] a){
    int lng = a.length;
    int min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
  public static long min(long[] a){
    int lng = a.length;
    long min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
////////////////////////////////////////////

}


Measured memory_bytes: 35704
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, V = MAP()
B, W = MAP()
T = INT()

if V <= W:
    print("NO")
elif abs(A-B) <= T*(V-W):
    print("YES")
else:
    print("NO")

    
    

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

#define ll long long

using namespace std;

int main(){
	int N, A[500010];
	ll RES = 0, res;

	cin >> N;

	A[0] = 0;
	for(int i = 1; i <= N; ++i){
		cin >> A[i];
		RES += abs(A[i] - A[i-1]);
	}

	A[N+1] = 0;
	RES += abs(A[N]);

	for(int i = 1; i <= N; ++i){
		res = RES;
		res -= abs(A[i] - A[i-1]);
		res -= abs(A[i+1] - A[i]);
		res += abs(A[i+1] - A[i-1]);
		printf("%lld\n", res);
	}

	return 0;
}


Measured memory_bytes: 1664
#include <cstdio>

using namespace std;

const int mod = 1000000007;
int p[600];
long long c[601];
long long dp[600][601];

long long calc(int x, int y) {
    int cnt = 0, i;
    
    if (dp[x][y] >= 0) return dp[x][y];
    if (y <= x) return dp[x][y] = 0;
    if ((y - x) % 2 == 1) return dp[x][y] = 0;
    
    for (i = x; i < y; i++) {
        if (p[i] == -1) {
            cnt++;
        } else if (p[i] < x || p[i] >= y) {
            return dp[x][y] = 0;
        }
    }
    
    dp[x][y] = c[cnt];
    
    for (i = x; i < y; i++) {
        dp[x][y] -= calc(x, i) * c[cnt] % mod;
        if (dp[x][y] < 0) dp[x][y] += mod;
        
        if (p[i] == -1) cnt--;
    }
    
    return dp[x][y];
}

int main() {
    int n, k, i, j, l;
    long long ans = 0;
    
    scanf("%d %d", &n, &k);
    
    n *= 2;
    
    for (i = 0; i < n; i++) p[i] = -1;
    
    for (i = 0; i < k; i++) {
        int a, b;
        
        scanf("%d %d", &a, &b);
        
        a--;
        b--;
        
        p[a] = b;
        p[b] = a;
    }
    
    for (i = 0; i < n; i++) {
        for (j = 0; j <= n; j++) {
            dp[i][j] = -1;
        }
    }
    
    c[0] = 1;
    for (i = 2; i <= n; i += 2) c[i] = c[i - 2] * (i - 1) % mod;
    
    for (i = 0; i < n; i++) {
        for (j = i + 1; j <= n; j++) {
            int cnt = 0;
            
            for (l = 0; l < i; l++) {
                if (p[l] == -1) cnt++;
            }
            
            for (l = j; l < n; l++) {
                if (p[l] == -1) cnt++;
            }
            
            ans += calc(i, j) * c[cnt] % mod;
            if (ans >= mod) ans -= mod;
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}


Measured memory_bytes: 2944
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
#include<string>
using namespace std;

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

#define INF INT_MAX/3
#define REP(i,n) for(int i=0;i<n;i++)

int main(){
	string str;
	vector<char> answer;
	cin>>str;
	int N = str.size();
	REP(i,N){
		if(i %2 == 0){
			answer.push_back(str[i]);
		}

	}
	for(auto& s:answer)cout<<s;
	cout<<endl;
	return 0;
}


Measured memory_bytes: 640
def exec_f(s, m)
  s1, s2 = s.chars

  if @l[s1].zero? && @l[s2].zero?
    puts 'No'
    exit 0
  elsif @l[s1].zero?
    @l[s1]+=1
    @l[s2]-=1
    @proc << s1
  elsif @l[s2].zero?
    @l[s1]-=1
    @l[s2]+=1
    @proc << s2
  else
    if m.nil?
      @l[s1]+=1
      @l[s2]-=1
      @proc << s1
    else
      t = (s.chars & m.chars).first
      nt = t == s1 ? s2 : s1
      @l[t] += 1
      @l[nt] -= 1
      @proc << t
    end
  end
end

n, a, b, c = gets.split.map(&:to_i)
@l = { 'A' => a, 'B' => b, 'C' => c }
@proc = []
commands = []
n.times do
  commands << gets.chop
end

n.times do
  s = commands.shift
  m = commands.shift

  exec_f(s, m)
  commands.unshift(m)
end
puts 'Yes'
@proc.each do |p|
  puts p
end


Measured memory_bytes: 25148
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  dp[0]=b=5-s[0]
  for i in range(1,w):
    dp[i]=b=b+(s[i-1]^s[i])
  for i in range(x,h*x,x):
    l=i-x
    dp[i]=dp[l]+(s[l]^s[i])
    for j in range(1,w):
      k=i+j
      sk=s[k]
      l=k-1
      t=dp[l]+(s[l]^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

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

int main() {
  int N; 
  cin>>N;
  vector<vector<int>> S(10,vector<int>(10,0));
  vector<vector<bool>> C(10,vector<bool>(10,true));
  for(int i=1;i<=N;i++){
    string s = to_string(i);
    int si=s.size();
    int a=(s.at(0)-'0');
    int b=(s.at(si-1)-'0');
    S.at(a).at(b)++;
  }
  int ans=0;
  rep(i,10){
    rep(j,10){
      if(C.at(i).at(j)){
        if(i==0||j==0) continue;
        int a=S.at(i).at(j),b=S.at(j).at(i),d;
        if(i!=j) d=2*a*b;
        else d=a*b;
        ans+=d;
        C.at(j).at(i)=false;
      }
    }
  }
  cout<<ans;
}

Measured memory_bytes: 3604
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    Set<Integer> set = new HashSet<>();
    set.add(a);
    set.add(b);
    set.add(c);
    System.out.println(set.size() == 2 ? "Yes" : "No");
  }
}

Measured memory_bytes: 22996
#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <stack> 
#include <queue> 
#include <string> 
using namespace std; 


int main()
{
	char c,d;
	d = 'Z';
  int i=1;
	while (cin >> c) {
		if (c!='h' && i%2==1) {
			cout << "No" << endl;
			return 0;
		}
      else if(c!='i'&&i%2==0){
      cout<<"No"<<endl;
      return 0;
      }
		i++;
	}
  if(i%2==0)cout<<"No"<<endl;
	else	cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll N,D;
int main(){
	cin>>N>>D;
	ll a=N-D-1;
	if(D==N-1) cout<<N-1<<endl;
	else if(D==1) cout<<N*(N-1)/2<<endl;
	else cout<<(N-D+2)*(N-D+1)/2 +D-3<<endl;
}

Measured memory_bytes: 3092