akhauriyash/Code-Regression huggingface dataset:
from collections import deque
import sys
input = sys.stdin.readline

mod = 10**9 + 7
INF = float("inf")

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

edges = [[] * N for _ in range(N)]
for _ in range(N - 1):
    # 頂点の番号を0-indexに直す
    a, b = map(lambda x: int(x) - 1, input().split())
    edges[a].append(b)
    edges[b].append(a)

# 0をrootとする
dq = deque([0])

# color[i] = i番目の頂点を塗ることが可能な色の数
# visitedの管理も兼ねている（別にvisited配列を作っても特に問題はない）
# 後述するように負の値が入ることを許しているので、-1や0などで初期化するのはNG
color = [INF] * N
color[0] = K

"""
root = 0 から末端に向かって調べる

子1, 子2, 子3, ...と複数の「未着色」の子がある場合、塗ることが出来る色の数は
K-1, K-2, K-3,... (p==0 の場合)
K-2, K-3, K-4,... (p!=0 の場合)　のようになる

子が十分多い場合、どこかで「0」になるので、ans = 0　となる
故に、色の数が負になっても答えには影響しない
"""

while dq:
    # 親となる頂点
    p = dq.popleft()
    # 親をpとした時の、「未着色」な子の数
    cnt = 0
    for c in edges[p]:
        if color[c] == INF:
            if p == 0:
                color[c] = (K - 1 - cnt) % mod
            else:
                color[c] = (K - 2 - cnt) % mod
            cnt += 1
            dq.append(c)

ans = 1
for i in range(N):
    ans = (ans * color[i]) % mod

print(ans)


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

int main() {
	string s;
	int ans = 0, most = 0, i;
	cin >> s;
	s += '\0';
	for (i = 0; s[i] != '\0'; i++) {
		if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
			ans++;
		}
		else {
		
		ans = 0;
		}
		if (ans > most) {
			most = ans;
		}
	}

	cout << most << endl;

}

Measured memory_bytes: 256
#include<stdio.h>
int main (void){
  long long int n, d,x[200000],y[200000];
  int ans,i;
  ans=0;
  scanf("%lld %lld",&n,&d);
  
  for(i=0;i<n;i++)
  {
    scanf("%lld %lld",&x[i],&y[i]);
  }
  for(i=0;i<n;i++)
  {
    if(x[i]*x[i]+y[i]*y[i]<=d*d){ans++;}
  }
  printf("%d\n",ans);
  
  return 0;
}

Measured memory_bytes: 4820
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{

  int n;
  int a,b; //生地の値段　トッピングの値段
  int c; //生地のカロリー
  int d[105];
  int cal[105] = {};
  int dol[105] = {};
  int ans[105] = {};
  int max;
  //生地のカロリーと載せたトッピングのカロリーの合計

  cin >> n;
  cin >> a >> b;
  cin >> c;

  for( int i=0;i<n;i++ ) cin >> d[i];


  sort(d,d+n,greater<int>()); //降順ソート

  for( int i=0;i<n;i++ ){
    cal[i] = c;
    dol[i] = a;
    for( int j=0;j<=i;j++ ){
      cal[i] += d[j];
    }
    dol[i] += (i + 1)*b;
    ans[i] = cal[i]/dol[i];
  }

  max = ans[0];
  for( int i=0;i<n;i++ ){
    if( max < ans[i] ) max = ans[i];
  }

  cout << max << endl;

  return 0;

}



Measured memory_bytes: 3168
#include<cstdio>
#include<iostream>
#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

bool cmp(int a,int b){
        return a>b;
}

int main(){

        ios::sync_with_stdio(false);
        cin.tie(0);

	long long int n,k;
	cin >> n >> k;

	bool check=0;
	if(n%k==0){
		check=1;
		cout<<"0";
	}
	
	if(check==0){
		long long int a = n/k;
		long long int tmp = n - a*k;
		cout << min(abs(tmp-k),tmp);



	}	

	return 0;
}	


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n, m, i, j;
    int sum = 0;
    cin >> n >> m;
    int A[1000][1000], b[1000];
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            cin >> A[i][j];
        }
    }
    for(i = 0; i < m; i++){
            cin >> b[i];
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
                sum += A[i][j] * b[j];    
        }
        cout << sum << endl;
        sum = 0;
    }
    
    return 0;
    
}



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

using namespace std;

int main() {
    int N;
    long long ans = 0;

    cin >> N;

    long long B[N - 1];
    for (int i = 0; i < N - 1; i++) {
        cin >> B[i];
    }

    ans += B[0];
    for (int j = 0; j < N - 2; j++) {
        ans += min(B[j], B[j + 1]);
    }
    ans += B[N - 2];

    cout << ans << endl;

    return 0;
}



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

using namespace std;
int main(void) {
    long MOD = 1e9 + 7;
    long n;
    cin >> n;
    string s;
    cin >> s;

    vector<bool> t(2*n);

    long k=0;
    for(int i=0; i<2*n; i++) {
        int c = s[i] == 'B' ? 1 : 0;
        if((c+k)%2 == 0) {k--; continue;}
        t[i] = true;
        k++;
    }
    //for(auto x: t) cout << x << endl;
    if(k!=0) {cout << 0 << endl; return 0;}

    long r = 1;
    long tt = 0;
    for(int i=0; i<2*n; i++) {
        if(t[i]) {
            // open
            tt++;
        } else {
            r *= tt;
            r %= MOD;
            tt--;
        }
    }
    for(int i=1; i<=n; i++)
        r *= i, r %= MOD;
    cout << r << endl;
}


Measured memory_bytes: 640
def solve():
    INF = 10**12

    def max2(x, y): return x if x >= y else y
    def min2(x, y): return x if x <= y else y

    N, K = map(int, input().split())
    Hs = [0] + list(map(int, input().split()))

    dp = [[INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        H = Hs[i]
        diffs = []
        for iPrev in range(i):
            diff = max2(0, H-Hs[iPrev])
            diffs.append(diff)
        dp[i][0] = 0
        dp[i][1] = H
        for j in range(2, min(i, N-K)+1):
            for iPrev in range(i):
                dp[i][j] = min2(dp[i][j], dp[iPrev][j-1]+diffs[iPrev])

    ans = min(dpi[N-K] for dpi in dp)
    print(ans)


solve()


Measured memory_bytes: 41584
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;

const long long INF = 1LL << 60;

int main() {
    int n;
    cin>>n;
    vector<int> h(n);
    rep(i,n) cin>>h[i];
    vector<ll> dp(n, INF);
    dp[0]=0;
    
    for(int i=1;i<n;i++){
        chmin(dp[i],dp[i-1]+abs(h[i]-h[i-1]));
        if(i>1) chmin(dp[i],dp[i-2]+abs(h[i]-h[i-2]));
    }
                      
    cout<<dp[n-1]<<endl;
    
    return 0;
}

Measured memory_bytes: 1408
import java.io.PrintWriter;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
	
	public static void main(String[] args) {
		// 入力
		final String w;
		try(Scanner scan = new Scanner(System.in)) {
			w = scan.next();	// 1≤|w|≤100
		}
		
		// 文字charに対応するIntegerごとに集計
		Map<Integer, List<Integer>> map = IntStream.range(0, w.length()).map(i -> w.charAt(i)).boxed()
				.collect(Collectors.groupingBy(i -> i));
			
		boolean result =map.keySet().stream().allMatch(key  -> map.get(key).size() % 2 == 0);
		
		// 出力
		try (PrintWriter out = new PrintWriter(System.out)) {
			out.println(result ? "Yes" : "No");
		}

	}

}

Measured memory_bytes: 16464
S = input()
len_S = 4 # 4 = len(input())

for i in range(1 << (len_S-1)):
  ops_list = ["+"]*(len_S-1)
  for j in range(len_S-1):
    
    if (i>>j)&1:
      ops_list[j] = "-"
  eq = ""
  for j in range(len_S-1):
    eq = eq + S[j] + ops_list[j]
    
  eq = eq + S[len_S-1]
  if eval(eq) == 7:
    print(eq + "=7")
    exit()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iomanip>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}
ll lcm(ll x,ll y){
  ll g=gcd(x,y);
  return x/g*y;
}


int main() {
  int N, M;
  scanf("%d %d",&N,&M);
  vector<vector<int>> ab(N);
  rep(i,M){
    int a, b; 
    scanf("%d %d",&a,&b);
    a--; b--;
    ab[a].push_back(b);
    ab[b].push_back(a);
  }
  
  bool ok = false;
  for(int u : ab[0]){
    for( int v : ab[u]){
      if(v == N-1){
        cout << "POSSIBLE" << endl;
        return 0;
      }
    }
  }  
  if(!ok) cout << "IMPOSSIBLE" << endl;  
}

  



Measured memory_bytes: 12016
program c

implicit none
integer :: I, J
character(4) :: S
character(9) :: ans
integer, dimension(4) :: A
character(1), dimension(4) :: B

read(*,*) S
read(S(1:1),*) A(1)
do I = 2, 4
read(S(I:I),*) A(I)
B(I) = "+"
end do

do I = 1, 2**3
 do J = 1, 3
  A(J+1) = abs(A(J+1))
  B(J+1) = "+"
  if (btest(I-1,J-1)) then
  A(J+1) = - A(J+1)
  B(J+1) = "-"
  end if
 end do
 if (sum(A)==7) exit
end do

do J = 1, 3
A(J+1) = abs(A(J+1))
end do

write(*,'(i0,a1,i0,a1,i0,a1,i0,a1,i0)') A(1),B(2),A(2),B(3),A(3),B(4),A(4),"=",7

end program

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _GLIBCXX_DEBUG
#define rep(i, c) for (int i = 0; i < (int)c; i++)
#define debug(x) cout << #x << " = " << x << endl
#define print(x) cout << x << endl;
const ll MOD = 1000000007;

vector<pair<ll, ll>> factorize(ll N)
{
    vector<pair<ll, ll>> res;
    for (ll i = 2; i * i <= N; i++)
    {
        if (N % i != 0)
            continue;
        ll ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % i == 0)
        {
            ++ex;
            N /= i;
        }

        res.push_back({i, ex});
    }

    // 最後に残った数
    if (N != 1)
        res.push_back({N, 1});
    return res;
}

int main()
{
    ll N;
    cin >> N;
    vector<pair<ll, ll>> A = factorize(N);

    vector<ll> cand;
    for (auto p : A)
    {
        for (ll i = 1; i <= p.second; i++)
        {
            cand.push_back(pow(p.first, i));
        }
    }

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

    ll ans = 0;
    for (ll i : cand)
    {
        if (N % i != 0)
        {
            continue;
        }
        else
        {
            N /= i;
            ans++;
        }
    }

    cout << ans << endl;
}


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

int main()
{
  int n;
  cin >> n;
  int a[n];
  rep(i, n) cin >> a[i];
  int res = 1e9;
  for(int y = -100; y <= 100; y++)
  {
    int sum = 0;
    rep(i, n)
    {
      sum += abs(a[i] - y) * abs(a[i] - y);
    }
    res = min(res, sum);
  }
  
  cout << res << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int i;
    int n, sum = 0;
    int money[6] = {1, 5, 10, 50, 100, 500};

    for(i = 0; i < 6; i++){
        scanf("%d", &n);
        money[i] *= n;
        sum += money[i];
    }
    printf("%d\n", (sum >= 1000));
    return 0;
}

Measured memory_bytes: 1836
package main

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

func partition1(a []int, p, r int) (ret int) {
	x := a[r]
	i := p - 1
	for j := p; j < r; j++ {
		if a[j] <= x {
			i++
			a[i], a[j] = a[j], a[i]
		}
	}
	a[i+1], a[r] = a[r], a[i+1]
	return i + 1
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)
	a := make([]int, n)
	for i := range a {
		a[i] = nextInt(sc)
	}
	p := partition1(a, 0, len(a)-1)
	wtr := bufio.NewWriter(os.Stdout)
	for i := 0; i < len(a); i++ {
		if i > 0 {
			fmt.Fprint(wtr, " ")
		}
		if i == p {
			fmt.Fprintf(wtr, "[%d]", a[i])
		} else {
			fmt.Fprint(wtr, a[i])
		}
	}
	fmt.Fprintln(wtr)
	wtr.Flush()
}
func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}



Measured memory_bytes: 3184
#include <iostream>

using namespace std;
const int INF = 1001001001;

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

    int ans = INF;
    for (int i = 0; i <= 200000; i += 2) {
        int cost = i * c;

        int x = X - i/2;
        int y = Y - i/2;
        cost += max(0, x) * a + max(0, y) * b;

        ans = min(ans, cost);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
from itertools import combinations
import math


def I(): return int(sys.stdin.readline().rstrip())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def S(): return sys.stdin.readline().rstrip()


def LS(): return list(sys.stdin.readline().rstrip().split())


A = I()
B = I()
C = I()
X = I()
ans = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if a*500+b*100+c*50 == X:
                ans += 1
print(ans)


Measured memory_bytes: 39536
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int h,w;
int main(){
  cin >> h >> w;
  vvi s(h, vi(w));
  int black = 0;
  rep(y, h){
    rep(x, w){
      char c;
      cin >> c;
      if(c == '.') s[y][x] = 1;
      else{
        s[y][x] = 0;
        black++;
      }
    }
  }
  vvi checked(h, vi(w,-1));
  checked[0][0] = 0;
  queue<vi> que;
  que.push({0,0});
  int ans = 0;
  while(!que.empty()){
    vi v = que.front();
    int posx = v[0]; int posy = v[1];
    que.pop();
    if(posx == w - 1 && posy == h - 1){
      ans = checked[posy][posx] + 1;
      break;
    }
    if(posx + 1 < w && checked[posy][posx + 1] == -1 && s[posy][posx + 1]){
      checked[posy][posx + 1] = checked[posy][posx] + 1;
      que.push({posx + 1, posy});
    }
    if(posy + 1 < h && checked[posy + 1][posx] == -1&& s[posy + 1][posx]){
      checked[posy + 1][posx] = checked[posy][posx] + 1;
      que.push({posx, posy + 1});
    }
    if(posx - 1 >= 0 && checked[posy][posx - 1] == -1 && s[posy][posx - 1]){
      checked[posy][posx - 1] = checked[posy][posx] + 1;
      que.push({posx - 1, posy});
    }
    if(posy - 1 >= 0 && checked[posy - 1][posx] == -1 && s[posy - 1][posx]){
      checked[posy - 1][posx] = checked[posy][posx] + 1;
      que.push({posx, posy - 1});
    }
  }
  if(ans > 0) cout << h * w - black - ans << endl;
  else cout << -1 << endl;
}

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

void Main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i, n)
    cin >> a[i];
    vector<int> b(n);
    REP(i, n)
    cin >> b[i];
    vector<int> c(n - 1);
    REP(i, n - 1)
    cin >> c[i];

    ll total = 0;
    for (int i = 0; i < a.size(); i++)
    {
        total = total + b[a[i] - 1];
        if (i > 0)
        {
            if (a[i] - 1 == a[i - 1])
            {
                total = total + c[a[i - 1] - 1];
            }
        }
    }
    cout << total << endl;
}

int main()
{
    std::cout << std::fixed << std::setprecision(15);
    Main();
}

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

int main(){
    int a,b,c,d,e;
    cin>>a>>b>>c>>d>>e;
    int f,g,h,i,j;
    int count=0;
    f=a%10;
    g=b%10;
    h=c%10;
    i=d%10;
    j=e%10;
    int m=900;

    if(!(f==0)&&!(g==0))m=min(f,g);
    else if(f==0&&g==0)count+=2;
    else if(f==0||g==0){
        count++;
        m=max(f,g);
    }
    if(!(h==0))m=min(m,h);
    else count++;
    if(!(i==0))m=min(m,i);
    else count++;
    if(!(j==0))m=min(m,j);
    else count++;
    if(count==5)count=4;
    if(m>10)m=0;
    int sum;
    sum=a+b+c+d+e+(40-f-g-h-i-j)+m-count*10;
    cout<<sum<<endl;
    //cout<<m<<endl;
    //cout<<count<<endl;
}

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

typedef vector<int> veci;
typedef pair<int,int> pii;
typedef vector<pii> vecii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vecl;
typedef vector<pll> vecll;
#define EPS (1e-9)
#define MOD (1e9+7)
#define fi first
#define se second

int main()
{
    ios::sync_with_stdio(false);
#ifdef LOCAL_TEST    
    int tcs;
    cin >> tcs;
    while (tcs-->0)
#endif        
{
    int n, m;
    cin >> n >> m;

    vector<veci> adj(n);
    int a, b;
    for (int i=0; i<m; ++i) {
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i=0; i<n; ++i)
        if (!adj[i].empty())
            sort(adj[i].begin(), adj[i].end());

    bool res = false;
    for (int i=0; i<int(adj[0].size()); ++i) {
        int vis = adj[0][i];
        if (!adj[vis].empty()) {
            auto it = lower_bound(adj[vis].begin(), adj[vis].end(), n-1);
            if (it!=adj[vis].end() && *it==n-1) {
                res = true;
                break;
            }
        }
    }

    cout << (res?"POSSIBLE":"IMPOSSIBLE") << endl;
}}

Measured memory_bytes: 12016
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-3;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;

string s; int n;
int alf[26]; int cnt[26];
string l, r;

ll bit[1 << 18];
void add(int a, ll w) {
	for (int i = a; i <= n + 1; i += i & -i)bit[i] += w;
}
ll sum(int a) {
	ll ret = 0;
	for (int i = a; i > 0; i -= i & -i)ret += bit[i];
	return ret;
}
vector<int> loc[26]; int cur[26];
int main() {
	cin >> s; n = s.length();
	rep(i, n)alf[s[i] - 'a']++;
	int c = 0; int chk = -1;
	rep(i, 26) {
		if (alf[i] % 2) {
			c++; chk = i;
		}
	}
	ll ans = 0;
	if (n % 2) {
		if (c != 1) {
			cout << -1 << endl;
			return 0;
		}
		else {
			int le = 0;
			rep(i, n) {
				int t = s[i] - 'a';
				if (cnt[t] < alf[t] / 2) {
					l.push_back('a' + t);
					ans += i - le; le++;
					cnt[t]++;
				}
				else {
					r.push_back('a' + t);
				}
			}
			rep(i, n - n / 2) {
				if (r[i] == 'a' + chk) {
					ans += i;
					r.erase(r.begin() + i);
					break;
				}
			}
			reverse(r.begin(), r.end());
		}
	}
	else {
		if (c > 0) {
			cout << -1 << endl; return 0;
		}
		else {
			int le = 0;
			rep(i, n) {
				int t = s[i] - 'a';
				if (cnt[t] < alf[t] / 2) {
					cnt[t]++;
					l.push_back('a' + t);
					ans += i - le; le++;
				}
				else {
					r.push_back('a' + t);
				}
			}
			reverse(r.begin(), r.end());
		}
	}
	rep(i, n / 2) {
		int t = r[i] - 'a';
		loc[t].push_back(i);
	}
	rep(i, n / 2) {
		int t = l[i] - 'a';
		//ans += loc[t][cur[t]] - i + (i-sum(loc[t][cur[t]] + 1));
		ans += loc[t][cur[t]] - sum(loc[t][cur[t]] + 1);
		add(loc[t][cur[t]]+1, 1);
		cur[t]++;
	}
	cout << ans << endl;
	//stop
	return 0;
}


Measured memory_bytes: 2180
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
typedef pair<pii, ll>pi3;
ll mod = 1000000007;
int main()
{
	int num;
	scanf("%d", &num);
	map<int, int>ma;
	for (int i = 0; i < num; i++)
	{
		int z;
		scanf("%d", &z);
		ma[z]++;
	}
	int ans = 0;
	map<int, int>::iterator it = ma.begin();
	for (;;)
	{
		if (it == ma.end())break;
		if ((*it).second < (*it).first)ans += (*it).second;
		else ans += (*it).second - (*it).first;
		it++;
	}
	printf("%d\n", ans);
}

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

int main(void){
    int MAX=0, ANS=0, a, i;
    for(i=0; i<3; i++){
        scanf("%d", &a);
        ANS += a;
        if(a > MAX) MAX = a;
    }
    printf("%d\n", 9*MAX+ANS);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
typedef pair<int, int> P;
typedef int64_t ll;
const int MAX_N = 10000;
const int INF = 1000000000;


int main() {
	int N;
	cin >> N;
	vector<int> d(N);
	rep(i, N) {
		cin >> d.at(i);
	}
	sort(d.begin(), d.end());
	int num = d.size() / 2;
	int ans = d.at(num) - d.at(num - 1);
	cout << ans << endl;

}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<int> p(n),cor(n);
	for(int i=0;i<n;i++)
	{
		cor[i] = i+1;
		cin >> p[i];
	}
	int cnt = 0;
	for(int i=0;i<n;i++)
	{
		if(cor[i] == p[i])
			cnt++;
	}
	if(cnt+2==n || cnt==n) cout << "YES" << endl;
	else cout << "NO" << endl;
}

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

int main()
{
  ll N, D, A;
  cin >> N >> D >> A;
  vector<pair<ll, ll>> XH(N);
  for (ll i = 0; i < N; i++)
  {
    ll x, h;
    cin >> x >> h;
    XH.at(i) = make_pair(x, h);
  }
  sort(XH.begin(), XH.end());

  vector<ll> X(N + 2), H(N + 2, 0);
  X.at(0) = -INF;
  for (ll i = 0; i < N; i++)
  {
    X.at(i + 1) = XH.at(i).first;
    H.at(i + 1) = XH.at(i).second;
  }
  X.back() = INF;

  vector<ll> dam(N + 2);
  dam.at(0) = 0;
  ll ans = 0;
  for (ll i = 1; i <= N; i++)
  {
    dam.at(i) += dam.at(i - 1);

    ll tmp = divceil(max(0LL, H.at(i) - dam.at(i)), A);
    ll y = A * tmp;
    ans += tmp;
    dam.at(i) += y;

    auto it = upper_bound(X.begin(), X.end(), X.at(i) + 2 * D);
    ll ind = it - X.begin();
    dam.at(ind) -= y;

    //cerr << i << " " << ind << " " << dam.at(i) << endl;
  }
  cout << ans << endl;
}

Measured memory_bytes: 8064
#include <iostream>
#include <vector>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> k(n), mm(m, 0);
  vector<vector<int>> a(n);
  rep(i, 0, n) {
    cin >> k[i];
    rep(j, 0, k[i]) {
      int b;
      cin >> b;
      a[i].push_back(b-1);
      mm[b-1]++;
    }
  }
  int c = 0;
  rep(i, 0, m) {
    if(mm[i] == n) {
      c++;
    }
  }
  cout << c;
}

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

int main () {
  int h, n;
  cin >> h >> n;
  int a[n], sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum += a[i];
  }
  if (sum >= h) cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
} 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n=nxtl();
    if(n%2)
    {
        cout<<"0\n";
        return 0;
    }
    ll test=0;
    ll y=(double)log(n)/(double)log(5);
    ll cur=5;
    for(ll i=1;i<=y;i++)
    {
        ll x=n/cur;
        x/=2;
        test+=x;
        cur*=5;
    }
    cout<<test<<endl;

    

    return 0;   
}


 
 


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];    
  }
  int ans = 1e9;
  for (int i = 1; i <= 300; i++) {
    int sum = 0;
    for (int j = 0; j < n; j++) {
      sum += (a[j] - i) * (a[j] - i);
    }
    ans = min(ans, sum);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
#define KAKUSUKO

#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X, Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define len(X) ((int)(X).size())
#define mod(n, m) (((n)%(m)+(m))%(m))
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 200000;
int N;
ll A[MAX_N];
ll S[MAX_N];

int main() {
    cin >> N;
    rep(i, N) cin >> A[i];

    S[0] = A[0];
    rep(i, 1, N - 1) {
        S[i] = S[i - 1] + A[i];
    }

    ll ans = INFLL;
    rep(i, N) {
        ll s1 = S[i];
        ll s2 = S[N - 1] - S[i];
        ans = min(ans, abs(s1 - s2));
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3328
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    print((a+b)%24)
    return

#B
def B():
    n, m = LI()
    ab = LIR(n)
    cd = LIR(m)
    for a, b in ab:
        ans = inf
        an = 0
        for num, cdi in enumerate(cd):
            c, d = cdi
            if ans > abs(a - c) + abs(b - d):
                ans = abs(a - c) + abs(b - d)
                an = num
        print(an+1) 
    return

#C
def C():
    n = II()
    ans = inf
    for i in range(1, int(math.sqrt(n)) + 1):
        if not n % i:
            ans = min(ans, max(int(math.log(i, 10)), int(math.log(n // i, 10))))
    print(ans+1)
    return

#D
def D():
    _, a, b = LI()
    v = LI()
    v.sort(reverse=True)
    d = defaultdict(int)
    ans = defaultdict(int)
    for vi in v:
        d[vi] += 1
    for i in range(a, b + 1):
        res = v[:i]
        r = res[-1]
        tmp = res.count(r)
        r = math.factorial(d[r]) / math.factorial(tmp) / math.factorial(d[r] - tmp)
        ans[sum(res) / i] += math.ceil(r-0.5)
    ans = list(ans.items())
    ans.sort(reverse=True, key = lambda x:x[0])
    print(ans[0][0])
    print(ans[0][1])
    return

#Solve
if __name__ == '__main__':
    D()


Measured memory_bytes: 39152
#include<stdio.h>
int insert(int A[101],int n)
{
	int i,j,k,v;
	for(i=1;i<n;i++)
	{
		for(k=0;k<n;k++)
		{
			printf("%d",A[k]);
			if(k!=n-1){printf(" ");}
			else{printf("\n");}
		}
		v=A[i];
		j=i-1;
		while(j>=0 && A[j]>v)
		{
			A[j+1]=A[j];
			j--;
		}
		A[j+1]=v;
	}
	for(k=0;k<n;k++)
	{
		printf("%d",A[k]);
		if(k!=n-1){printf(" ");}
		else{printf("\n");}
	}
	return 0;
}
int main(void)
{
	int n,i,A[101];
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{scanf("%d",&A[i]);}
	insert(A,n);

	return 0;
}

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

constexpr int INF = 1e9;
constexpr int STORE = 0;

struct Order {
  int t, n, id, dst;
};

struct Position {
  int u, v, du, dv;
};

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

  // input
  int V, E, T;
  cin >> V >> E;
  vector<vector<int>> adjacency_matrix(V, vector<int>(V, INF));
  for (int i = 0; i < E; i++) {
    int u, v, d;
    cin >> u >> v >> d;
    u--, v--;
    adjacency_matrix[u][v] = adjacency_matrix[v][u] = d;
  }
  cin >> T;
  vector<Order> orders(T);
  for (int i = 0; i < T; i++) {
    orders[i].t = i;
    cin >> orders[i].n;
    if (orders[i].n) {
      cin >> orders[i].id >> orders[i].dst;
      orders[i].dst--;
    }
  }

  // solve
  // Warshall-Floyd algorithm
  vector<vector<int>> distance_matrix = adjacency_matrix;
  for (int i = 0; i < V; i++) distance_matrix[i][i] = 0;
  vector<vector<int>> next_node_matrix(V, vector<int>(V));
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      next_node_matrix[i][j] = j;
    }
  }
  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        if (distance_matrix[i][k] + distance_matrix[k][j] < distance_matrix[i][j]) {
          distance_matrix[i][j] = distance_matrix[i][k] + distance_matrix[k][j];
          next_node_matrix[i][j] = next_node_matrix[i][k];
        }
      }
    }
  }

  vector<int> commands(T);
  Position position{STORE, STORE, 0, 0};
  queue<int> destinations;
  queue<Order> produced_orders;
  for (int t = 0; t < T; t++) {
    if (orders[t].n) {
      produced_orders.push(orders[t]);
    }
    if (position.du == 0 && position.u == STORE || position.dv == 0 && position.v == STORE) {
      while (!produced_orders.empty()) {
        destinations.push(produced_orders.front().dst);
        produced_orders.pop();
      }
      destinations.push(STORE);
    }

    if (position.du == 0) {
      while (!destinations.empty() && destinations.front() == position.u) destinations.pop();
    } else if (position.dv == 0) {
      while (!destinations.empty() && destinations.front() == position.v) destinations.pop();
    }
    if (destinations.empty()) {
      commands[t] = -1;
    } else if (position.du == 0 || position.dv == 0) {
      int i = position.du == 0 ? position.u : position.v;
      int j = next_node_matrix[i][destinations.front()];
      commands[t] = j;
      position = {i, j, 1, adjacency_matrix[i][j] - 1};
    } else {
      if (position.du + distance_matrix[position.u][destinations.front()] <
          position.dv + distance_matrix[position.v][destinations.front()]) {
        commands[t] = position.u;
        position.du--;
        position.dv++;
      } else {
        commands[t] = position.v;
        position.du++;
        position.dv--;
      }
    }
  }

  // output
  for (auto e : commands) cout << e + (e != -1) << '\n';
  cout << flush;
}


Measured memory_bytes: 2432
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::fmt::Debug;

fn main() {
    let mut sc = Scanner::new();
    let h = sc.parse::<usize>();
    let w = sc.parse::<usize>();
    let n = sc.parse::<usize>();
    let mut a = (0..n).map(|_| {
        return sc.parse::<i32>();
    }).collect::<Vec<i32>>();

    let mut map = vec![vec![0; w]; h];
    let mut cur = 0;
    for i in 0..h {
        if i % 2 == 0 {
            for j in 0..w {
                a[cur] -= 1;
                map[i][j] = cur + 1;
                if a[cur] == 0 {
                    cur += 1;
                }
            }
        } else {
            for j in (0..w).rev() {
                a[cur] -= 1;
                map[i][j] = cur + 1;
                if a[cur] == 0 {
                    cur += 1;
                }
            }
        }
    }

    for i in 0..h {
        for j in 0..w {
            print!("{} ", map[i][j])
        }
        println!("")
    }
}

struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

Measured memory_bytes: 4352
/* 実行時間1s制限の場合
  10^6 1,000,000   : 余裕をもって間に合う
  10^7 10,000,000  : おそらく間に合う
  10^8 100,000,000 : 非常にシンプルな処理でないと厳しい
 */
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; // long longはデータモデル(LLP64, LP64, ...)によらず64bit.
ll gcd(ll a, ll b) {return b ? gcd(b, a%b) : a;}  // Greatest Common Divisor ユークリッドの互除法（aが長辺）
vector<pair<ll,int>> factorize(ll n) {            // a,bの公約数 = GCD(a, b)の約数
    vector<pair<ll,int>> res;
    for (ll i = 2; i*i <= n; i++) { // √nまで探せばよい
        if (n%i) continue;
        res.emplace_back(i, 0);     // 割り切れたら
        while (n%i == 0) {
            n /= i;
            res.back().second++;
        }
    }
    if (n != 1) res.emplace_back(n, 1); // この時点で1でなかったら、残りは素数.
    return res;
}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}         // Least Commont Multiple オーバーフローしないように先に割る
ll ceil(ll a, ll b) {return (a+b-1)/b;}

const ll INF = LONG_MAX;
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; }

ll f(ll h)
{
    if (h == 1) return 1;
    return 2*f(h/2) + 1;
}

int main(int argc, char* argv[])
{
#ifdef LOCAL
    // 以降 cin の入力元が 'xxx.txt' になる
    // std::ifstream in(argv[1]);
    //std::cin.rdbuf(in.rdbuf());
    //std::ifstream in(string(argv[0]) + ".txt");
    std::ifstream in("in.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    ll h;
    cin >> h;

    cout << f(h);



    return 0;
}

/*
  - 1e9 : 10^9
  - container一般
    - 合計
      accumulate(a.begin(), a.end(), 0LL)  0LLはオーバーフロー用
  - vector
    vector<int> A(N, 0); // 0で初期化(省略可)
    - loop
      for  (int i = 0; i < A.size(); i++) {}
      for  (int elem : A) {}
    - sort
      std::sort(v.begin(), v.end());  // 昇順
      std::sort(v.begin(), v.end(), std::greater<int>()); //降順
      - vector<vector<int>> cnt(h, vector<int>(w))
    - sort(struct)
        struct st_t {
            string name;
            int p;
            bool operator<(const st_t& another) const {
                if (name == another.name)
                {
                    return p > another.p;
                }
                return name < another.name;
            }
        };
        vector<st_t> st(n);
        sort(st.begin(), st.end());
  - pair
    - pairのソートの定義 : firstが優先的に比較。同じだったらsecond。
    - pair<pair<string,int>,int> p[110];
      std::sort(p,p+a);
        こうすると、first.first -> first.second -> secondの順にソートされる
    - sort
      - sort(a.begin(), cb.end(), greater<pair<int, int>>());
  - map
    - for (auto x : map) {}  // x.first:key  x.second:value.
  - priority_queue<int> q;
    - q.top()に最大値が入っている
  - string
    - loop
      for (char& c : s) {}
 */



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

int main() {
	int a, b, gcd, lcm;
	while(cin >> a >> b){
		gcd = 1;
		lcm = 1;
		for(int i = 2; a != 1 || b != 1; i++) {
			while(a % i == 0 || b % i == 0) {
				if(a % i == 0 && b % i == 0){
					a = a / i;
					b = b / i;
					gcd = gcd * i;
					lcm = lcm * i;
				} else if(a % i == 0) {
					a = a / i;
					lcm = lcm * i;
				} else if(b % i == 0) {
					b = b / i;
					lcm = lcm * i;
				}
			}
		}
		cout << gcd << " " << lcm << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
import collections
h,w = map(int, raw_input().split(' '))
mat = [raw_input() for _ in range(h)]


def bfs(cur, mat):
	q = collections.deque([(cur,0)])
	vis =  set([])
	temp = 0
	while(q):
		u, dis = q.popleft()
		vis.add(u)
		i,j = u
		temp = max(temp, dis)
		for nei in [(i+1, j), (i-1,j), (i,j-1), (i,j+1)]:
			if 0 <= nei[0]< len(mat) and 0<= nei[1] < len(mat[nei[0]]) and (nei not in vis) and (mat[nei[0]][nei[1]] == '.'):
				vis.add(nei)
				q.append((nei, dis +1))
		

	return temp


m = 0
for i in range(len(mat)):
	for j in range(len(mat[i])):
		if mat[i][j] == '.': 
			m = max(m, bfs((i,j), mat))
print m

Measured memory_bytes: 34024
/*zxj*/
#include<iostream> 
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<sstream>
#define sf scanf
#define pf printf
#define pfn printf("\n");
#define pfk printf(" ");
#define pf0 printf("0");
#define pf1 printf("1");
#define ll long long
#define sfd(n) scanf("%d",&n);
#define sfdd(n,m) scanf("%d%d",&n,&m);
#define sfld(n) scanf("%lld",&n);
#define sfldd(n,m) scanf("%lld%lld",&n,&m);
#define sflf(n) scanf("%lf",&n);
#define sflff(n,m) scanf("%lf%lf",&n,&m);
#define sfc(n) scanf("%c",n);
#define sfcc(n,m) scanf("%c%c",n,m);
#define sfs(n) scanf("%s",n);
#define sfss(n,m) scanf("%s%s",n,m);
#define pfd(n) printf("%d",n);
#define pfld(n) printf("%lld",n);
#define pflf(n) printf("%lf",n);
#define pfc(n) printf("%c",n);
#define pfs(n) printf("%s",n);
using namespace std;
#define csh(a,n) memset(a,n,sizeof(a));
int main(){
	int n;
	cin>>n;
	double arr[100];
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	for(int i=0;i<n-1;i++){
		sort(arr,arr+n);
		arr[0]=(arr[0]+arr[1])/2;
		arr[1]=10000000;
	}
	cout<<arr[0]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;
typedef vector<map<lli,lli>> graph;

#ifndef N
#define N 100002
#endif
#ifndef MOD
#define MOD 1000000007
#endif

lli exeuclid(lli a,lli aa,lli x,lli xx,lli y,lli yy){
	lli q;
	if(a == 0) return aa > 0 ? xx : -xx;
	q = aa / a;
	return exeuclid(aa - q * a,a,xx - q * x,x,yy - q * y,y);
}

lli invarse(lli x){
	return (exeuclid(MOD,x,0,1,1,0) + MOD) % MOD;
}


lli factrial(lli x){
	static lli dp[N];
	if(dp[x]) return dp[x];
	if(x == 0) 	return dp[x] = 1;
				return dp[x] = (factrial(x-1) * x) % MOD;
}

lli combination(lli n,lli k){
	if(k < 0 || k > n) return 0;
    return (((factrial(n) * invarse(factrial(k))) % MOD) * invarse(factrial(n-k))) % MOD;
}

lli n;
vll a;
vll v;
lli l;

int main(){
	cin >> n;
	v = vll(n+1,-1);
	n++;
	a = vll(n);
	for(lli i = 0;i < n;i++){
		cin >> a[i];
		if(v[a[i]] >= 0) l = i - v[a[i]];
		else v[a[i]] = i;
	}
	for(lli k = 1;k <= n;k++){
		lli z = n-k;
		cout << (combination(n,z) - combination(n-(l+1),z-l) + MOD)%MOD << endl;
	}

	return 0;

}

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

int main(void)
{
    int n,m;
    cin >>n>>m;
    int a[n][m], b[m], c[n];
    for(int i=0;i<n;i++) c[i] = 0;
    for(int i=0;i<n;i++) {
        for (int j=0;j<m;j++){
            cin >>a[i][j];
        }
    }
    for(int i=0;i<m;i++) cin >>b[i];

    for(int i=0;i<n;i++) {
        for (int j=0;j<m;j++){
            c[i] += a[i][j]*b[j];
        }
    }
    for(int i=0;i<n;i++) printf("%d\n",c[i]);
    return 0;
}


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

#define ll long long
using namespace std;
const int mod = 1e9 + 7, N = 1007;
int n, m;
int dp[N][N];
char grid[N][N];

int solve(int i, int j) {
    if (i == n - 1 && j == m - 1)return 1;
    if (i >= n || j >= m || grid[i][j] == '#')return 0;
    int &ret = dp[i][j];
    if (~ret)return ret;
    return ret = (solve(i + 1, j) + solve(i, j + 1)) % mod;
}

int main() {
    cin >> n >> m;
    ll sum = 0;
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < n; ++i)for (int j = 0; j < m; ++j)cin >> grid[i][j];
    cout << solve(0, 0);
    return 0;
}


Measured memory_bytes: 5248
#include "bits/stdc++.h"
using namespace std;
int main(){
  int H,W; cin >> H >>W;
  vector<vector<char>> m(H+2,vector<char>(W+2,'@'));
  for(int i = 1; i <= H;++i)for(int j =1 ; j<=W;j++)cin>>m[i][j];
  int dx[8] = {0,1,1,1,0,-1,-1,-1};
  int dy[8] = {-1,-1,0,1,1,1,0,-1};
  vector<vector<int>> v(H+2,vector<int>(W+2,-1));
  for(int i = 1; i <= H;++i)for(int j =1 ; j<=W;j++){
    if(m[i][j]=='#')continue;
    int cnt=0;
    for(int k=0;k < 8;k++){
      int nx = i+dx[k],ny=j+dy[k];
      if(m[nx][ny]=='#')cnt++;
    }
    v[i][j]=cnt;
  }
  for(int i = 1; i <= H;++i){
    for(int j =1 ; j<=W;j++){
      if(v[i][j]==-1)cout<<'#';
      else cout<<v[i][j];
    }
    cout<<endl;
  }
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define vec vector

int main(void)
{
	int n;
	cin >> n;
	vec<int> a(2 * n - 1);
	rep(i, 2 * n - 1) cin >> a[i];

	int left = 1;
	int right = 2 * n - 1;
	int k;
	while(1) {
		k = (left + right + 1) / 2;
		vec<int> b(2 * n - 1, 1);
		rep(i, 2 * n - 1) if (a[i] < k) b[i] = 0;
		int mid = n - 1;
		int ans = - 1;
		rep(i, n - 1) {
			if (b[mid - i] == b[mid - i - 1]) ans = b[mid - i];
		   	if (b[mid + i] == b[mid + i + 1]) ans = b[mid + i];
			if (ans != - 1) break;
		}
		if (ans == - 1) ans = b[0];
		if (ans) left = k;
		else right = k - 1;
		if (left == right) {
			k = left;
			break;
		}
	}
	cout << k << endl;
	return 0;
}

Measured memory_bytes: 1920
/*
ID: 
TASK: Shiritori
LANG: C++                 
*/
#define usingfile1
#include <iostream>
#include <cstdio>
#include <set>
int file_reopen(){
	freopen("task.in","r",stdin);
	freopen("task.out","w",stdout);
}
using namespace std;
set <string> s;
void main_program(){
	int n;cin>>n;
	s.clear();
	bool seiritsu=1;
	string l,w;
	for(int i=1;i<=n;++i){
		l=w;
		cin>>w;
		if(s.count(w)>0){
			seiritsu=0;
		}
		s.insert(w);
		if(i==1)continue;
		if(l[l.length()-1]!=w[0]){
			seiritsu=0;
		}
	}
	printf(seiritsu?"Yes":"No");
	printf("\n");
}
int main(){
	ios::sync_with_stdio(0);
	#ifdef usingfile
	file_reopen();
	main_program();
	fclose(stdin);fclose(stdout);
	#else
	main_program();
	#endif
	return 0;
}


Measured memory_bytes: 256
program main
  implicit none
  integer :: n, m, i, pos, l, r, dice(100000), idice
  character(100001) :: s
  read *, n, m
  read *, s
  pos = n
  idice = 0
  outer: do
    l = max(0, pos - m)
    r = pos - 1
    do i = l, r
      if (s(i + 1:i + 1) == "0") then
        idice = idice + 1
        dice(idice) = pos - i
        pos = i
        if (i == 0) then
          exit outer
        else
          cycle outer
        end if
      end if
    end do
    print "(i0)", -1
    return
  end do outer
  dice(1:idice) = dice(idice:1:-1)
  print "(100000(i0, ' '))", dice(1:idice)
end program main


Measured memory_bytes: 1316
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
signed main()
{
    string s;
    cin >> s;
    int cnt = 0;
    int lcnt = 0;
    rep(i, s.size()) {
        if (i == 0 && s[i] != 'A') {
            put("WA");
            return 0;
        }
        if (2 <= i && i <= s.size() - 2) {
            if (s[i] == 'C') cnt ++;
        }
        if ('a' <= s[i] && s[i] <= 'z') {
            lcnt ++;
        }
    }

    if (lcnt == s.size() - 2 && cnt == 1) {
        put("AC");
        return 0;
    }

    put("WA");

    return 0;
}

Measured memory_bytes: 3628
import java.util.*;
import java.io.PrintWriter;
import java.math.BigInteger;

class Main{
	void solve(){
		int N=cin.nextInt();
		int M=cin.nextInt();
		int R=cin.nextInt();

		if(N*M>R){
			cout.println(0);
			return;
		}

		int RR=R-N*M;
		//(RR+N-1)C(RR)
		BigInteger ans=new BigInteger("1");
		for(int i=2;i<=RR+N-1;i++){
			ans=ans.multiply(new BigInteger(""+i));
		}
		for(int i=2;i<=RR;i++){
			ans=ans.divide(new BigInteger(""+i));
		}
		for(int i=2;i<=N-1;i++){
			ans=ans.divide(new BigInteger(""+i));
		}
		cout.println(ans);
	}
	//-----------------------------------------------------

	public static void main(String args[]){
		cin=new Inputer();
		cout=new PrintWriter(System.out);
		new Main().solve();
		cout.flush();
	}

	static class Inputer{
		private static Scanner sc;
		Inputer(){
			sc=new Scanner(System.in);
		}
		String next(){
			return sc.next();
		} 
		int nextInt(){
			return Integer.parseInt(sc.next());
		}
		long nextLong(){
			return Long.parseLong(sc.next());
		}
		double nextDouble(){
			return Double.parseDouble(sc.next());
		}
		char[] nextCharArray(){
			return sc.next().toCharArray();
		}
	}

	private static Inputer cin;
	private static PrintWriter cout;
}

Measured memory_bytes: 284772
M1,D1 = (int(i) for i in input().split())
M2,D2 = (int(i) for i in input().split())

next_month = M1+1
if M1+1 > 12:
  next_month = (M1+1)%12


if next_month == M2 and D2 == 1:
  print(1)
else:
  print(0)


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

int main() {
  int N;
  cin >> N;
  vector<int> card(N);
  for (int i=0; i<N ; i++){
    cin >> card.at(i);
  }
  sort(card.begin(),card.end());
  reverse(card.begin(),card.end());
  int Alice=0;
  int Bob=0;
  for (int i=0; i<N;){
    Alice=Alice+card.at(i);
    i=i+2;
  }
  for (int i=1; i<N;){
    Bob=Bob+card.at(i);
    i=i+2;
  }
  cout << Alice-Bob << endl;

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner scan = new Scanner(System.in);
        
        int x = scan.nextInt();
        int y = scan.nextInt();
        
        System.out.print(x*y);
        System.out.print(" ");
        System.out.println(2*(x+y));
    }
}



Measured memory_bytes: 26104
#include <string>
#include <algorithm>
#include <vector> 
#include <math.h>
#include <iostream>
using namespace std;
long long mod = 1000000000 + 7;


int main()
{
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s ;
	
	vector<int> stand;
	vector<int> reverse;
	int n_switch = 0;
	//とりあえず最初の人は逆立ちしてることにする．
	if (s[0] == '0') {
		reverse.push_back(0);
		n_switch++;
	}

	bool first = true;
	char flag = s[0];
	int a = 0;
	for (int i = 0; i < n; i++) {
		
		if (flag != s[i]) {
			if (s[i] == '1') {
				stand.push_back(a);
			}
			else {
				reverse.push_back(a);
			}
			a = 0;
			n_switch++;
			flag = s[i];
		}

		a++;
	}
	
	

	//最後についても逆立ちしてることにする．
	if (s[n - 1] == '0') {
		stand.push_back(a);
		reverse.push_back(0);
	}
	else {
		reverse.push_back(a);
	}
	
	int ans = 0;
	int now = 0;
	if (k >= stand.size()) {
		ans = n;
	}
	else {
		ans = ans + reverse[0];
		for (int i = 0; i < k; i++) {
			ans = ans + stand[i] + reverse[i + 1];
		}
		now = ans;
		for (int i = 0; i < stand.size() - k; i++) {
			now = now - stand[i] - reverse[i] + stand[i + k] + reverse[i + k + 1];
			ans = max(ans, now);
		}
	}

	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 1020