akhauriyash/Code-Regression huggingface dataset:
def warshallFloyd():
    for i in range(V):
        for j in range(V):
            if dp[j][i] == INF: continue
            for k in range(V):
                if dp[i][k] == INF: continue
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return
INF = 10 ** 18
V, E = map(int, input().split())
dp = [[INF for _ in range(V)] for _ in range(V)]
ansF = False
for i in range(V):
    for j in range(V):
        if i == j:
            dp[i][j] = 0


for i in range(E):
    s, t, d = map(int, input().split())
    dp[s][t] = d

warshallFloyd()
for i in range(V):
    if dp[i][i] < 0:
        print('NEGATIVE CYCLE')
        exit()
        
for i in range(V):
    for j in range(V):
        if dp[i][j] == INF:
            ptmp = 'INF'
        else:
            ptmp = dp[i][j]
        if j != V - 1:
            print(ptmp, end=' ')
        else:
            print(ptmp)


Measured memory_bytes: 6280
n = int(input())
p = list(map(int,input().split()))

ans=0

def swap(i,j):
    b = p[i]
    p[i] = p[j]
    p[j] = b

for i in range(n-1):
    if i+1==p[i]:
        swap(i,i+1)
        ans+=1

if p[n-1]==n:
    ans+=1

print(ans)

Measured memory_bytes: 53420
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e4 + 5;
ll n, m, k, sum;
string s, r;

int main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(); cout.tie();
    cin>>n;
    cin>>s;
    m = s.length();
    if(n >= m){
        cout<<s;
    }
    else{
        for(int i = 0; i < n; i++)
            cout<<s[i];
        cout<<"...";
    }
    return 0;
}


Measured memory_bytes: 3612
N,M = map(int,input().split())

H=list(map(int,input().split()))

dist = [ [] for _ in range(N+1)]

for i in range(M):
    a,b = map(int,input().split())
    dist[a].append(b)
    dist[b].append(a)


c=0
for i,it in enumerate(dist[1:]):
    hi = list(map(lambda x:H[x-1],it))

    if (list(filter(lambda x:H[i]<=x,hi)).__len__()==0):
        c+=1
    
print(c)

    

Measured memory_bytes: 31168
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <iterator>
#include <bitset>
#include <random>
#include <assert.h>
#include <unordered_map>
#include <array>
#include <ctime>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define X first
#define Y second
#define MP make_pair
#define umap unordered_map

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> P;
typedef unsigned int uint;

struct List{
	int val, cnt;
	List *next;
};

List lv[10010];
int cur;
List *head0, *tail2;

pair<List*, List*> split(List* li, int x){
	//if (li == nullptr) return nullptr;
	if (li->cnt <= x) return split(li->next, x - li->cnt);
	List *ret = &lv[cur++];
	ret->val = li->val, ret->cnt = li->cnt - x, ret->next = li->next;
	li->cnt = x, li->next = ret;
	if (tail2 == li) tail2 = ret;
	return MP(li, ret);
}

int count(List *li, int x){
	if (x <= 0) return 0;
	if (li->val == 0) return count(li->next, x - li->cnt);
	if (li->cnt < x) return li->cnt + count(li->next, x - li->cnt);
	return x;
}

void shuffle(int x, int y){
	List *tail0, *head1;
	tie(tail0, head1) = split(head0, x);
	List *tail1, *head2;
	tie(tail1, head2) = split(head1, y - x);

	// h0->t0->h1->t1->h2->t2
	// h2->t2->h1->t1->h0->t0
	tail2->next = head1;
	tail1->next = head0;
	tail0->next = nullptr;
	head0 = head2, tail2 = tail0;
}

int main(){
	int n;
	while (cin >> n, n){
		int m, p, q, r;
		cin >> m >> p >> q >> r;

		MEMSET(lv, 0);
		cur = 0;
		head0 = &lv[cur++];
		head0->cnt = r;
		head0->val = 1;
		head0->next = &lv[cur];
		tail2 = &lv[cur++];
		tail2->cnt = n - r;
		tail2->val = 0;
		tail2->next = nullptr;

		while (m--){
			int x, y;
			cin >> x >> y;
			shuffle(x, y);
		}
		cout << count(head0, q) - count(head0, p-1) << endl;
	}

	return 0;
}

Measured memory_bytes: 1932
N=int(input())
h=list(map(int,input().split()))
dp=[0]*N
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(1,N-1):
    dp[i+1]=min(dp[i-1]+abs(h[i+1]-h[i-1]),dp[i]+abs(h[i+1]-h[i]))

print(dp[-1])

Measured memory_bytes: 52208
h, w = gets.chomp.split.map(&:to_i)
map = Array.new(h).map{Array.new(w)}
h.times do |i|
	map[i] = gets.chomp.split("")
end

ih = {}
jh = {}
h.times do |i|
	if map[i].uniq.length == 1 && map[i][0] == "."
		ih[i] = true
	else
		ih[i] = false
	end
end
mapt = map.transpose
w.times do |i|
	if mapt[i].uniq.length == 1 && mapt[i][0] == "."
		jh[i] = true
	else
		jh[i] = false
	end
end

h.times do |i|
	w.times do |j|
		print(map[i][j]) if ih[i] == false && jh[j] == false
	end
	puts if ih[i] == false
end


Measured memory_bytes: 14792
n = int(input())
s = input()
ans = s.count('R') * s.count('G') * s.count('B')
for i in range(n-2):
  for j in range(i+1, n-1):
    if j - i > n - j - 1:
      break
    if s[i] != s[j] and s[j] != s[2*j-i] and s[2*j-i] != s[i]:
      ans -= 1
print(ans)

Measured memory_bytes: 9020
MOD = 10**9 + 7

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs

def getCombNs(n, invs, MOD):
    combNs = [1] * (n//2+1)
    for k in range(1, n//2+1):
        combNs[k] = (combNs[k-1] * (n-k+1) * invs[k]) % MOD
    return combNs + combNs[:(n+1)//2][::-1]

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

invs = getInvs(N, MOD)

comb1s = getCombNs(N-K+1, invs, MOD)
comb2s = getCombNs(K-1, invs, MOD)

anss = []
for i in range(1, K+1):
    if N-K+1 < i or K-1 < i-1:
        ans = 0
    else:
        ans = comb1s[i] * comb2s[i-1] % MOD
    anss.append(ans)

print('\n'.join(map(str, anss)))


Measured memory_bytes: 3316
/************************************************************
	>>--> Author: Frederick
	>>--> Mail: 197***3881@qq.com
************************************************************/
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
#define ull unsigned long long
#define CIN ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn=2e5+5;
const ll MOD=1e9+7;
const int INF = 0x3f3f3f3f;

int main(){
    CIN;
    int n,k;
    cin>>n>>k;
    if(n*500>=k) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
	return 0;
}



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

#pragma warning(disable : 4996)

typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))
#define min3(x, y, z) min(x, min(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif

using namespace std;
//#define int long long;

double dist(double x1, double y1, double x2, double y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
ll idist(ll x1, ll y1, ll x2, ll y2) {
  return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

signed main() {
  ll N, K;
  cin >> N >> K;
  vector<ll> p(N);
  vector<ll> c(N);
  rep(i, N) {
    cin >> p[i];
    p[i]--;
  }
  rep(i, N) {
    cin >> c[i];
  }
  // dout << scoresum << endl;
  ll ans = -10e17;
  if (K > N) {
    rep(i, N) {
      // K>Nのとき何周かする
      ll d = 0;
      ll r = i;
      ll cnt = 0;
      ll lp = 0;
      while (r != i or cnt == 0) {
        cnt++;
        lp += c[r];
        r = p[r];
      }
      if (lp > 0) {
        d = lp * (K / cnt -1 );
      }
      //cout << cnt <<endl;
      /*
      dout << "------------------" << endl;
      dout << d << endl;
      dout << "------------------" << endl;
      */
      ll w = i;  //現在位置
      //いいかんじになるまでぐるぐるする(ヤバそうだったら累積和)
      ll g = c[w];
      for (ll j = 1; j <=cnt + K % cnt; j++) {
        d += c[w];
        g = max(d, g);
        w = p[w];
        // dout << "-" << i << " " << j << " " << d << endl;
      }
      ans = max(ans, g);
    }
  } else {
    rep(i, N) {
      ll d = 0;
      ll w = i;  //現在位置
      //いいかんじになるまでぐるぐるする(ヤバそうだったら累積和)
      ll g = c[w];
      for (ll j = 1; j <= K; j++) {
        d += c[w];
        g = max(d, g);
        w = p[w];
        // dout << "-" << i << " " << j << " " << d << endl;
      }
      ans = max(ans, g);
    }
  }

  cout << ans;
}


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

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

    int o = 0;
    for(int i = 0; i <= a; i++)
        for (int j = 0; j <= b; j++)
            for (int k = 0; k <= c; k++)
                if(10 * i + 2 * j + k == x / 50) o++;
    cout << o << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	int n, m, l[100000], r[100000], l1 = 0, r1 = 100001, ans;
	cin >> n >> m;
	for (int a = 0; a < m; a++) {
		cin >> l[a] >> r[a];
		if (l1 < l[a])l1 = l[a];
		if (r1 > r[a])r1 = r[a];
	}
	ans = r1 - l1 + 1;
	if (ans < 0)ans = 0;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
#define MOD 1000000007
using ll = long long;
using namespace std;
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 (a>b) { a=b; return 1; } return 0; }

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int a, b;
cin >> a >> b;
int res = 0;
reps(i,b+1,a){
    string s = to_string(i);
    string _s = s;
    reverse(_s.begin(),_s.end());
    if(s==_s){
        res++;
    }
}
cout << res <<endl;

//system("pause");
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,n) for(int i=1;i<(int)(n);i++)

typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) { //最大公約数
  if (b==0) return a;
  else return gcd(b, a%b);
}

ll lcm(ll a, ll b) { //最小公倍数
  return a * b / gcd(a, b);
}

ll digit_sum(ll a){ //10進桁和
  ll ans=0;
  while(a>0){
    ans+=a%10;
    a/=10;
  }
  return ans;
}



int main()
{
  string s;
  ll k,one_len=0;
  cin>>s>>k;
  ll tmp=0;
  if(s[tmp]=='1')one_len++;
  while(tmp<s.length()-1){
    if(s[tmp]=='1'&&s[tmp+1]=='1'){
      one_len++;
      tmp++;
    }else{
      break;
    }
  }

  if(one_len>=k){
    cout<<1<<endl;
  }else{
    cout<<s[one_len]<<endl;
  }
  return 0;
}


Measured memory_bytes: 3628
#include<stdio.h>
int main(){

  int n,m;
  scanf("%d %d",&n,&m);
  if(n == m)printf("Draw\n");
  if(n == 1) n = 14;
  if(m == 1) m = 14;
  if(n > m)printf("Alice\n");
  else if(m > n)printf("Bob\n");


return 0;}


Measured memory_bytes: 128
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define max(x,y)(x>y?x:y)
#define min(x,y)(x>y?y:x)
#define MOD (int)1e9+7
int dx4[]={1,0,-1,0};
int dy4[]={0,-1,0,1};
typedef long long int ll;
typedef unsigned long long int ull;
ll gcd(ll x,ll y){if(!y)return x;return gcd(y,x%y);}
ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
void swap(ll *x,ll *y){ll tmp=*x;*x=*y;*y=tmp;}
int asc_cmp(const void* X,const void* Y){ll x=*(int*)X,y=*(int*)Y;if(x<y)return -1;else if(x==y)return 0;else return 1;}
int desc_cmp(const void* X,const void* Y){ll x=*(int*)X,y=*(int*)Y;if(x<y)return 1;else if(x==y)return 0;else return -1;}
typedef struct pair_{
    int x;
    int y;
}pair_t;

int main(){
    int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;scanf("%d",&k);
    printf("%d\n",a[k-1]);
}

Measured memory_bytes: 128
import numpy as np
n, m, x = map(int, input().split())
c = [0] * n
a = np.zeros((n, m))
for i in range(n):
    t = [int(j) for j in input().split()]
    c[i] = t[0]
    a[i] = t[1:]
low = float('inf')
for i in range(2 ** n):
    price = 0
    score = np.zeros(m)
    for j in range(n):
        if i & (1 << j):
            score += a[j]
            price += c[j]
    if len(score[score >= x]) == m:
        low = min(low, price)
print(-1) if low==float('inf') else print(low)

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

using namespace std;

int N;
string S;

int main() {
	cin >> S;
	N = S.size();
	bool ans = true;

	for (int i = 0; i <= N / 2; i++) {
		if (S[i] != S[N - 1 - i]) {
			ans = false;
		}
	}
	const int first = (N - 1) / 2 - 1;
	for (int i = 0; i <= first / 2; i++) {
		if (S[i] != S[first - i]) {
			ans = false;
		}
	}
	const int second = (N + 3) / 2 - 1;
	for (int i = 0; i < N - second; i++) {
		if (S[i + second] != S[N - 1 - i]) {
			ans = false;
		}
	}

	if (ans) { cout << "Yes" << endl; }
	else { cout << "No" << endl; }
}

Measured memory_bytes: 256
def main():
    from itertools import groupby
    from math import ceil
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    t = input()

    q = {'r': p, 's': r, 'p': s}
    ans = 0
    for i in range(k):
        j = t[i::k]

        for key, group in groupby(j):
            g = list(group)
            ans += q[key] * ceil(len(g)/2)

    print(ans)

if __name__ == '__main__':
    main()


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

// int/long:		-2,147,483,648 - 2,147,483,648 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536,870,912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

#define	MOD 1000000007

int	main() {
	int N;
	string S;
	cin >>N >>S;
	if (0!=N%2) {
		cout <<"No" <<endl;
		return 0;
	}
	N /=2;
	for (int i=0; i<N; i++) {
		if (S.at(i)!=S.at(i+N)) {
			cout <<"No" <<endl;
			return 0;
		}
	}
	cout <<"Yes" <<endl;
	return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		int count = 0;
		for(int i = 0; i < n - 1; i++) {
			int j = n - 1;
			while(j > i) {
				if(arr[j - 1] > arr[j]) {
					int v = arr[j];
					arr[j] = arr[j - 1];
					arr[j - 1] = v;
					count++;
				}
				j--;
			}
		}
		for(int i = 0; i < n; i++) {
			if(i == n - 1) {
				System.out.println(arr[i]);
			} else {
				System.out.print(arr[i] + " ");
			}
		}
		System.out.println(count);
	}
}



Measured memory_bytes: 26228
import math
N = int(input())
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
# print(combinations_count(4, 2))
G = N //3
ans = 0
mod = 10**9+7
for i in range(1,G+1):
    K = N - 3 * i
    # aa = (K+1)**(i-1)
    # bb = math.factorial(i-1)
    ans += (combinations_count(K+i-1,K))% mod
print(ans%mod)


Measured memory_bytes: 9040
N, Q = map(int, input().split())
S = input()

a = [0] * N
c = 0

for i in range(N-1):
    if S[i:i+2] == "AC":
        c += 1
    a[i + 1] = c

l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
for i in range(Q):
    print(a[r[i] - 1] - a[l[i] - 1])

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

int main()
{
	double _t, t, y, N;
	while (cin >> _t){
		t = _t / 9.8;
		y = 4.9 * t * t;
		N = (y + 5) / 5;

		cout << static_cast<int>(N+1) << endl;
	}
	return 0;
}

Measured memory_bytes: 1232
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
 
##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力
 
# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと
 
##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順
 
# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    ans = {
    "SUN": 7,
    "MON": 6,
    "TUE": 5,
    "WED": 4,
    "THU": 3,
    "FRI": 2,
    "SAT": 1
    }
    S = input()
    S = S[:-1]
    
    print(ans[S])
    
    
if __name__ == "__main__":
	main()


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll extgcd(ll a,ll b,ll& x,ll& y){
  ll d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
ll mod_inverse(ll a,ll m){
  ll x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
ll MOD=1000000007LL;

ll dp[1111][1111];
ll fact[1111],facti[1111];
ll po[1111][1111];
int main(){
  ll n,a,b,c,d;
  cin>>n>>a>>b>>c>>d;

  
  fact[0]=facti[0]=1;
  for(ll i=1;i<=n;i++){
    fact[i]=(fact[i-1]*i)%MOD;
    facti[i]=(facti[i-1]*mod_inverse(i,MOD))%MOD;
    assert((fact[i]*facti[i])%MOD==1);
  }
  
  for(ll i=1;i<=n;i++){
    po[i][0]=1LL;
    for(ll j=1;i*j<=n;j++){
      po[i][j]=((po[i][j-1])*facti[i])%MOD;
    }
  }
  
  dp[0][a]=1;
  for(ll i=a;i<=b;i++){
    for(ll j=0;j<=n;j++){
      if(dp[j][i]==0) continue;
      (dp[j][i+1]+=dp[j][i])%=MOD;
      for(ll k=c;k<=d;k++){
	if(j+i*k>n) break; 
	(dp[j+i*k][i+1]+=((dp[j][i]*po[i][k])%MOD)*facti[k])%=MOD;
      }
    }
  }

  /*//
  for(ll j=0;j<=n;j++)
    for(ll i=a;i<=b+1;i++) 
      cout<<dp[j][i]<<" \n"[i==b+1];
  //*/

  ll ans=1LL;
  for(ll i=1;i<=n;i++) (ans*=i)%=MOD;
  cout<<(ans*dp[n][b+1])%MOD<<endl;
  return 0;
}


Measured memory_bytes: 13056
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  n <- getl toInt
  unless (n == (-1)) $ do
    print . solve $ n
    main
    
solve :: Int -> Int
solve n = 4280 - (bill n)
  where
    bill n
      | n <= 10 = 1150
      | n <= 20 = 1150 + 125 * (n - 10)
      | n <= 30 = 2400 + 140 * (n - 20)
      | otherwise = 3800 + 160 * (n - 30)

toInt :: String -> Int
toInt = read

getl :: (String -> a) -> IO a
getl f = f <$> getLine

Measured memory_bytes: 4040
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static readonly long Mod = 1000000000 + 7;

        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var N = Sarray()[0];
            var Ai = Sarray();
            var max = (long)Pow(3, N);
            var oddnum = 1;
            foreach(var a in Ai)
            {
                if (a % 2 == 0)
                    oddnum *= 2;
            }
            WriteLine(max - oddnum);
            //Out.Flush();
        }
    }
}

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

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for (int i=0; i<n; i++) cin>>a[i];
    int ans = 0;
    sort(a.begin(), a.end());
    for (int i = 0; i<n-2; i++) {
        int j1 = i+1;
        while (j1 < n-1 && a[j1] == a[i]) j1++;
        for (int j=j1; j<n-1; j++) {
            int k1 = j+1;
            while (k1<n && a[k1] == a[j]) k1++;
            for (int k = k1; k<n; k++) {
                if (a[k] < a[i] + a[j]) ans++;
                else break;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

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

int main(){
    int n, k; cin>> n >> k;
    vector<int> h(n);
    for(int i = 0;i<n;i++){
        cin>>h[i];
    }
    ll ans = 0;
    sort(h.begin(), h.end());
    for(int i = 0; i < n-k; i++){
        ans += (ll) h[i]; 
    }
    cout<<ans<<endl;
    return 0;

}

Measured memory_bytes: 1024
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	char S[200010];
	fread(S, 1, 200010, stdin);

	int L = 0, R = 200000;
	while (L + 1 < R) {
		int M = (L + R) / 2;
		if (S[M] >= '?') L = M;
		else R = M;
	}

	int r = R / 8 * 8;
	ll* owa = (ll*)(S + R);
	for (ll* kaki = (ll*)S; kaki < owa; kaki++) {
		ll tmp = *kaki;
		tmp += 0x0303030303030303;
		tmp ^= 0x0101010101010101;
		tmp += 0x0101010101010101;
		tmp &= 0xfcfcfcfcfcfcfcfc;
		*kaki = tmp;
	}
	for (int i = r; i < R; i++) {
		if (S[i] == '?') S[i] = 'D';
	}
	fwrite(S, 1, R, stdout);

	Would you please return 0;
}

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

#define ll unsigned long long
#define fi first
#define se second
#define pb push_back
#define mod 1000000007

using namespace std;

ll n;
string s;
char c;

int main()
{
    set < char > a;
    for (ll i=0; i<3; i++) cin >> c, a.insert(c);
    if (a.size()>1) cout << "Yes"; else cout << "No";
}


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

int main(){
        int n, i, j;
        while(cin >> n && n != 0){
                int ans = 1e6;
                vector<int> a(n);
                for (i = 0; i < n; i++) cin >> a[i];
                for (i = 0; i < n - 1; i++){
                        for (j = i + 1; j < n; j++){
                                ans =min(ans, abs(a[i] - a[j]));
                        }
                }
                cout << ans << endl;
        }
        return 0;
}



Measured memory_bytes: 3060
require 'pp'

n = gets.to_i
a, b = gets.split.map(&:to_i)
p_n = gets.split.map(&:to_i)

memo = {
    a: 0,
    b: 0,
    c: 0, 
}

p_n.each do |i|
   if i <= a
        memo[:a] += 1
   elsif i <= b
        memo[:b] += 1
   else
        memo[:c] += 1
   end
end

puts memo.values.min


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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define what_is(x) cerr << #x << " is " << x << endl;

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int a, b, k;
	cin >> a >> b >> k;
	vi v;
	for (int i = 1; i <= min(a, b); i++) {
		if (a%i == 0 && b%i == 0) v.push_back(i);
	}

	sort(all(v), greater<int>());
	cout << v[k-1] << endl;
}


Measured memory_bytes: 256
/*
 * 競技プログラミング用テンプレート
 * by yuma140902
 * 2019/12/07
 * ver 0.0.0
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 900000;
const ll INFL = 9000000;

#define vi vector<int>
#define vii vector<vector<int> >
#define vi_def(n) vector<int>((n))
#define vii_def(n,m) vector<vector<int> >((n), vector<int>((m)))
#define vi_def_dflt(n, def) vector<int>((n), (def))
#define vii_def_dflt(n, m, def) vector<vector<int> >((n), vector<int>((m), (def)))

#define rep(i, n) for(int i=0; i < (n); ++i)
#define per(i, n) for(int i=(n)-1; i >= 0; --i)
#define range(i, begin, end) for(int i=(begin); i < (end); ++i)

void printMinOutwardPath(int sx, int sy, int tx, int ty);
void printMinReturnPath(int sx, int sy, int tx, int ty);

int sx, sy, tx, ty;
int main(){
  scanf("%d %d %d %d", &sx, &sy, &tx, &ty);
  printMinOutwardPath(sx, sy, tx, ty);
  printMinReturnPath(sx, sy, tx, ty);

  printf("L");
  printMinOutwardPath(sx-1, sy, tx, ty+1);
  printf("D");

  printf("R");
  printMinReturnPath(sx, sy-1, tx+1, ty);
  printf("U");

  printf("\n");
}

// 往路
void printMinOutwardPath(int sx, int sy, int tx, int ty) {
  rep(i, ty - sy){
    printf("U");
  }
  rep(i, tx - sx){
    printf("R");
  }
  
}

// 復路
void printMinReturnPath(int sx, int sy, int tx, int ty) {
  rep(i, ty - sy){
    printf("D");
  }
  rep(i, tx - sx){
    printf("L");
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

ll dp[100005];


int main(){
    ll x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    ll p[a], q[b], r[c];
    rep(i, a) cin >> p[i];
    rep(i, b) cin >> q[i];
    rep(i, c) cin >> r[i];
    
    int ans = 0;

    sort(p, p+a, greater<>());
    sort(q, q+b, greater<>());
    sort(r, r+c, greater<>());
    

    rep(i, x) dp[0] += p[i];
    rep(i, y) dp[0] += q[i];

    priority_queue<ll, vector<ll>, greater<ll>> rq, gq;
    rep(i, x) rq.push(p[i]);
    rep(i, y) gq.push(q[i]);

    rep(i, c){
        ll u = r[i];
        rq.push(u);
        ll tmp1 = rq.top();

        gq.push(u);
        ll tmp2 = gq.top();

        dp[i+1] = dp[i];
        if(tmp1>tmp2){
            dp[i+1] += (u-tmp2);
            gq.pop();
        }else{
            dp[i+1] += (u-tmp1);
            rq.pop();
        }
    }

    cout << dp[c] << endl;
    // printf("%d\n", N);
    return 0;
}



Measured memory_bytes: 6260
#124 b
n=int(input())
h=list(map(int,input().split()))
ans=1
for i in range(1,n):
    best=h[i]
    for j in range(i):
        if best<h[j]:
            best=h[j]
    if best==h[i]:
        ans+=1
print(ans)

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

const int N = 100005;

int n, x;
long long lim = 0;

struct test {
    int b, l, r;

    long long val() const {
        return 1LL * b * l + 1LL * (x - b) * r;
    }
} a[N];

long long get_max(long long u) {
    int cnt = u / x;
    long long pre = 0, mx = 0;
    for (int i = 1; i <= cnt; i++) {
        pre += a[i].val();
    }
    u %= x;
    for (int i = 1; i <= n; i++) {
        long long cur = pre;
        if (i <= cnt) {
            cur -= a[i].val();
            cur += a[cnt + 1].val();
        }
        mx = max(mx, cur + min(1LL * a[i].b, u) * a[i].l + max(0LL, u - a[i].b) * a[i].r);
    }
    return mx;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].b >> a[i].l >> a[i].r;
        lim += 1LL * a[i].b * a[i].l;
    }
    sort(a + 1, a + n + 1, [](const test &a, const test &b) {
        return a.val() > b.val();
    });
    long long le = 0, ri = 1LL * x * n - 1;
    while (le <= ri) {
        long long mi = (le + ri) / 2;
        if (get_max(mi) >= lim) {
            ri = mi - 1;
        } else {
            le = mi + 1;
        }
    }
    cout << le << '\n';
}


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

int main() {
  int N,A,B,X;
  cin >>N>>A>>B;
  X = A*N ;
  
  if (X>B){
    cout<< B << endl;
  }
  else if (X<B){
    cout << X <<endl;
  }
  else{
    cout<< B<<endl;
  }
}


Measured memory_bytes: 256
r, c = map(int, input().split())
row = []
for i in range(r):
  row.append(input().split())
  row[i] = [int(n) for n in row[i]]
  rowsum = 0
  for j in range(c):
    rowsum += row[i][j]
    # print(row[i][j], end=" ")
  row[i].append(rowsum)
  # print(row[i][c])

# for i in range(r):
#   for j in range(c+1):
#     print(row[i][j], end=' ')
#   print()

calsum = []
for i in range(r):
  if calsum == []:
    for k in range(c+1):
      calsum.append(0)
  for j in range(c+1):
      calsum[j] += row[i][j]

# for i in range(c+1):
#   if i==c:
#     print(calsum[i])
#   else:
#     print(calsum[i],end=' ')

for i in range(r):
    print(" ".join(list(map(str, row[i]))))
print(" ".join(list(map(str, calsum))))




Measured memory_bytes: 5684
#include <iostream>
#define MAX 100000
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    int A[MAX];
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int ans = 1;
    int state = 0;
    for (int i = 1; i < N; i++) {
        if (A[i] > A[i-1]) {
            if (state == 0) state = 1;
            else if (state == -1) {
                ans++;
                state = 0;
            }
        }
        else if (A[i] < A[i-1]) {
            if (state == 0) state = -1;
            else if (state == 1) {
                ans++;
                state = 0;
            }
        }
    }

    cout << ans << '\n';
}


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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

int pw(int a, int b, int m = MOD) {
    if (b == 0)return 1;
    if (b & 1)return a * pw(a, b - 1) % m;
    return pw(a * a % m, b / 2);
}

int inverse(int a) {
    return pw(a, MOD - 2);
}

int fact[maxn], inv[maxn];

void preprocess(int lmt) {
    fact[0] = 1;
    for (int i = 1; i <= lmt; i++)fact[i] = (fact[i - 1] * i) % MOD;
    inv[lmt] = inverse(fact[lmt]);
    for (int i = lmt - 1; i >= 0; i--)inv[i] = (i + 1) * inv[i + 1] % MOD;
}

int C(int n, int r) {
    if (r > n)return 0;
    return fact[n] * inverse(fact[r] * fact[n - r] % MOD) % MOD;
}

void solve() {
    preprocess(maxn - 1);
    int n, k;
    cin >> n >> k;

    vector<int> v(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    int maxS = 0;
    int prev = LLONG_MIN;
    int id = 0;
    for (int i = k - 1; i < n; i++) {
        maxS = (maxS + v[i] * C(i, k - 1) % MOD) % MOD;
    }
    sort(v.rbegin(), v.rend());
    int minS = 0;
    prev = LLONG_MAX, id = 0;
    for (int i = k - 1; i < n; i++) {
        minS = (minS + v[i] * C(i, k - 1) % MOD) % MOD;
    }
    int ans = (maxS - minS + MOD) % MOD;
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 2560
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;
using namespace std;
typedef long long int LL;
typedef unsigned long long int ULL;

int main() {
    string str;
    cin >> str;
    vector<int> v;
    for (char x : str) {
        v.push_back(atoi(&x));
    }

    for (int bit = 0; bit < (1 << 3); bit++) {
        string res;
        res = to_string(v[0]);
        int ans = v[0];
        rep(i, 3) {
            if (bit & (1 << i)) {
                res += "+";
                ans += v[i + 1];
            } else {
                res += "-";
                ans -= v[i + 1];
            }
            res += to_string(v[i + 1]);
        }
        if (ans == 7) {
            cout << res <<  "=7" << endl;
            return 0;
        }

    }
    return 0;
}


Measured memory_bytes: 256
from collections import Counter

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

d = Counter(a)

ans = 0

for i, c in d.items():
    ans += d[i] * (d[i] - 1) // 2

for i in a:
    ans_ = ans
    ans_ -= d[i] * (d[i] - 1) // 2
    ans_ += (d[i] - 1) * (d[i] - 2) // 2

    print(ans_)

Measured memory_bytes: 89448
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#pragma GCC optimize ("O2")
#pragma GCC optimize ("tree-vectorize")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define popcnt(x) __builtin_popcount(x)
#define popcntll(x) __builtin_popcountll(x)
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class BTemplateMatching {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        int N, M;
        in>>N>>M;
        vc<string> A(N), B(M);
        REP(i, N) in>>A[i];
        REP(i, M) in>>B[i];
        REP(i, N-M+1) REP(j, N-M+1){
            bool ok = true;
            REP(k, M) REP(l, M){
                if(B[k][l]!=A[i+k][j+l]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                out<<"Yes\n";
                return;
            }
        }
        out<<"No\n";
    }
};


int main() {
	BTemplateMatching solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin >> s;
  string ans;
  
  if(s.at(0) == s.at(1) && s.at(1) == s.at(2)) {
    ans = "No";
  } else {
    ans = "Yes";
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
using namespace std;
typedef long long ll;
int h[100010];
int main() {
  int n, m, a, b;
  cin >> n >> m;
  vector<vector<int>> G(n);
  rep(i,n)
    cin >> h[i];
  rep(i,m)
  {
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  int cnt = 0;
  rep(i,n)
  {
    rep(j,G[i].size())
    {
      if (h[i] <= h[G[i][j]]) {
        cnt++;
        break;
      }
    }
  }
  cout << n - cnt;
}


Measured memory_bytes: 8804
#include<stdio.h>
int main()
{
	int x,a,b,d;
	scanf("%d%d%d",&x,&a,&b);
	
	if((b-1)<a)puts("delicious");
	else if((b-1)<a+x)puts("safe");
	else puts("dangerous");
	
	return 0;
}

Measured memory_bytes: 128
//AtCoder ABC117 A - Entrance Examination
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
int main() {
    double T,X; cin>>T>>X;
    auto ans=T/X;
    cout<<fixed<<std::setprecision(10)<<ans<<endl;
    return 0;
}

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

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<pair<int,int>> tasks;
    for (int i = 0; i < n; ++i) {
        int a,b;
        cin>>a>>b;
        tasks.emplace_back(b,a);
    }
    sort(tasks.begin(),tasks.end());
    int t=0;
    for (int i = 0; i < n; ++i) {
        if(t+tasks[i].second>tasks[i].first){
            cout<<"No"<<endl;
            return 0;
        }
        t+=tasks[i].second;
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 2420
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

typedef long long ll;

const ll inf = 1 << 30;
const ll mod = 1000000000 + 7;

template<typename T> T gcd(T a, T b)
{
	return b ? gcd(b, a % b) : a;
}


template<typename T> T lcm(T a, T b)
{
	return a / gcd(a, b) * b;
}

ll f(ll x, ll c, ll d)
{
	ll res = x;
	res -= x / c;
	res -= x / d;
	res += x / lcm(c, d);
	return res;
}

int main()
{
	ll a, b, c, d;
	cin >> a >> b >> c >> d;


	cout << f(b, c, d) - f(a - 1, c, d) << endl;
}


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

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

int main() {
    int N, M; cin >> N >> M;
    vector<int> A(M), B(M);
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
    }

    int ans = 0;
    for (int i = 0; i < M; i++) {
        UnionFind uf(N);
        for (int j = 0; j < M; j++) {
            if (i == j) continue;
            uf.unite(A[j], B[j]);
        }
        if (!uf.same(A[i], B[i])) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3468
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define base 31
#define MOD 1e9+7
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORs(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, a, b) for(int i = a; i < b; i++)
#define __FOR(i, a, b, k) for(int i = a; i <= b; i+= k)
#define __REP(i, a, b, k) for(int i = a; i < b; i+= k)
#define pb push_back
#define _io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define Read_ freopen("input.inp", "r", stdin)
#define Write_ freopen("output.out", "w", stdout);
using namespace std;
typedef pair <int, int> ii;
typedef vector <ii> vii;
#define fi first
#define se second
#define mp make_pair
#define N  200005
#define wb(x) ((x)<0?-(x):(x))

using namespace std;

int coord[20], pos[1<<16];
long long minn[1<<16], maxx[1<<16];

int main()
{
     _io; 
	int n, d, i, j, k, m, a, b;
	long long x;

	scanf("%d", &n);
	d=2;
	m = 1<<(d-1); 
	for(i = 0; i < m; ++i) 
	{
		minn[i] = 1e15;
		maxx[i] = -1e15;
		if(i)
		{
			pos[i] = 1; a = i^(i>>1); b = (i-1)^((i-1)>>1); k = a^b; 
			while(k%2 == 0) 
				++pos[i],
				k >>= 1;
			if(b < a) 
				pos[i] = -pos[i];
		}
	}
	while(n--)
	{
		for(j = 0; j < d; ++j)
			scanf("%d", &coord[j]);
		x = 0;
		for(k = 0; k < d; ++k) 
			x += coord[k];
		if(x < minn[0])
			minn[0] = x;
		if(x > maxx[0])
			maxx[0] = x;
		for(j = 1; j < m; ++j) 
		{
			x += 2*coord[wb(pos[j])-1]*(pos[j] > 0 ? 1 : -1); 
			if(x < minn[j])
				minn[j] = x;
			if(x > maxx[j])
				maxx[j] = x;
		}
	}
	x = -1;
	for(i = 0; i < m; ++i)
		if(wb(maxx[i]-minn[i]) > x)
			x = wb(maxx[i]-minn[i]);
	printf("%lld\n", x);
	return 0;
}


Measured memory_bytes: 3808
s = list(input())
s.append(0)
s.append(0)
s.append(0)
l =len(s)
while l>3:
    if s[0]=="d" and s[1]=="r" and s[2]=="e" and s[3]=="a" and s[4]=="m" and s[5]=="e" and s[6]=="r":
        if s[7]=="a":
            del s[0]
            del s[0]
            del s[0]
            del s[0]
            del s[0]
            l =len(s)
        else:
            del s[0]
            del s[0]
            del s[0]
            del s[0]
            del s[0]
            del s[0]
            del s[0]
            l =len(s)          
    elif s[0]=="d" and s[1]=="r" and s[2]=="e" and s[3]=="a" and s[4]=="m":
      del s[0]
      del s[0]
      del s[0]
      del s[0]
      del s[0]
      l =len(s)                    
    elif s[0]=="e" and s[1]=="r" and s[2]=="a" and s[3]=="s" and s[4]=="e" and s[5]=="r":
      del s[0]
      del s[0]
      del s[0]
      del s[0]
      del s[0]
      del s[0]
      l =len(s)
    elif s[0]=="e" and s[1]=="r" and s[2]=="a" and s[3]=="s" and s[4]=="e":
      del s[0]
      del s[0]
      del s[0]
      del s[0]
      del s[0]
      l =len(s)
    else:
        print("NO")
        break
if s[0]==0:
    print("YES")

Measured memory_bytes: 4212
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

void solve(ll N, ll K, vector<ll> l) {
  sort(l.rbegin(), l.rend());
  cout << accumulate(begin(l), begin(l) + K, 0LL) << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll N;
	ll K;
	scanf("%lld", &N);
	vector<ll> l(N-1+1);
	scanf("%lld", &K);
	for (int i = 0 ; i <= N-1 ; i++) {
	  scanf("%lld", &l[i]);
	}
	solve(N, K, l);
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int n,m,i;
  scanf("%d %d",&n,&m);
  int a[1001],all=0,count=0;
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    all=all+a[i];
  }
  for(i=0;i<n;i++){
    if(a[i]*4*m>=all){
      count++;
    }
  }
  if(count>=m)
    printf("Yes");
  else
    printf("No");  
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;

int main(){
    int64_t x,y;
    cin>>x>>y;
    int64_t res = abs(abs(x)-abs(y));
    if(x>=0){
        if(y>x){
            res+=0;
        }else if(0<y){
            res+=2;
        }else{
            res++;
        }
    }else{
        if(y<=0 && x<y){
            res+=0;
        }else if(y<x){
            res+=2;
        }else{
            res++;
        }
    }
    cout<<res<<endl;
    
    
    return 0;
}


Measured memory_bytes: 256
import functools

import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


N, M = map(int, input().split())
# reqs[i]: i 番目の島から行けないようにしたい、最小の島番号 (i < reqs[i])
reqs = [INF for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    reqs[a] = min(reqs[a], b)

ans = 0
# 最後に壊した橋の右側の島番号
broken = INF
# 後ろから壊していく
for i in reversed(range(len(reqs))):
    req = reqs[i]
    if req < broken:
        # 一番左壊しとけばその先には行けない
        broken = i + 1
        ans += 1
print(ans)


Measured memory_bytes: 7616
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int n,m,a[N],cnt,cur,ans,mx,sgnl,sgnr,tmp;
vector<int> rec[N];
int t[N << 2];
void modify(int l,int r,int val,int x=1,int lp=1,int rp=cnt) {
  if (l > rp || r < lp) return;
  if (l <= lp && rp <= r)
    return (void)(t[x] += val);
  int mid = (lp + rp) >> 1;
  modify(l,r,val,x<<1,lp,mid);
  modify(l,r,val,x<<1|1,mid+1,rp);
}
int query(int p,int x=1,int lp=1,int rp=cnt) {
  if (lp == rp) return t[x];
  int mid = (lp + rp) >> 1;
  if (p <= mid) return query(p,x<<1,lp,mid) + t[x];
  else return query(p,x<<1|1,mid+1,rp) + t[x];
}
signed main() {
  scanf("%lld%lld",&n,&m);
  cnt = 1;
  for (int i = 1 ; i <= n ; ++ i) {
    scanf("%lld",&a[i]);
    if (a[i] < a[i-1]) ++ cnt, ans += m;
    rec[a[i]].push_back(cnt);
    if (i != 1) ans += a[i] - a[i-1];
  }
  tmp = 1;
  for (int i = 1 ; i <= n ; ++ i)
    if (a[i] < a[i-1]) {
      ++ tmp;
      modify(tmp,tmp,m - a[i-1] - 1);
      cur += m - a[i-1] - 1;
    }
  // cerr << ans << endl;
  sgnl = 1;
  for (int i = 1 ; i <= m ; ++ i) {
    int l = 1, r = cnt;
    if (sgnl) ++ l;
    if (sgnr) -- r;
    modify(l,r,1);
    cur += r - l + 1;
    mx = max(mx,cur);
    // cerr << i << "： " << cur << endl;
    for (int j = 0 ; j < (int)rec[i].size() ; ++ j) {
      tmp = query(rec[i][j]);
      cur -= tmp+1;
      modify(rec[i][j],rec[i][j],-tmp-1);
    }
    if (i == a[n]) sgnr = 1, cur ++;
    if (i == a[1]) sgnl = 0;
  }
  ans -= mx;
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 8320
# include <bits/stdc++.h>
# define INF 1e9
using namespace std;

int main(){

  int N;
  string S;
  cin >> N >> S;

  vector<int>prefixW, suffixE;
  prefixW.push_back(0); // prefixW[i]: the number of 'W' in S[0], ... , S[i-1]
  suffixE.push_back(0); // suffixE[i]: the number of 'E' in S[i], ... S[N-1]

  for(int i=0; i<N; ++i){
    int v = 0;
    if(S[i] == 'W') v = 1;
    prefixW.push_back(prefixW.back()+v);
  }

  for(int i=N-1; i>=0; --i){
    int v = 0;
    if(S[i] == 'E') v = 1;
    suffixE.push_back(suffixE.back()+v);
  }
  reverse(suffixE.begin(), suffixE.end());

  int ans = N;
  for(int i=0; i < N; i++){
    int count;
    count = prefixW[i] + suffixE[i+1];
    ans = min(ans, count);
  }

  cout << ans << endl;

}


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

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

  string s;
  cin >> s;
  if(s == "Sunny"){
    cout << "Cloudy\n";
  }else if(s == "Cloudy"){
    cout << "Rainy\n";
  }else{
    cout << "Sunny\n";
  }
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
int cnt[202020];
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  //d
  int n;
  cin >> n;
  long long sum = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    cnt[a]++;
    sum += a;
  }
  int q;
  cin >> q;
  while (q--) {
    int b, c;
    cin >> b >> c;
    sum -= 1LL * b * cnt[b];
    sum += 1LL * c * cnt[b];
    cnt[c] += cnt[b];
    cnt[b] = 0;
    cout << sum << '\n';
  }
  return 0;
}

Measured memory_bytes: 3992
#include<cstdio>

using namespace std;



int main(void){

	int S=0,T=0,s;

	for(int i=0;i<4;i++){
		scanf("%d",&s);
		S+=s;
	}
	for(int i=0;i<4;i++){
		scanf("%d",&s);
		T+=s;
	}
	if(S>T) printf("%d\n",S);
	else printf("%d\n",T);

	return 0;
}

Measured memory_bytes: 1020