akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <stdio.h>
 
using namespace std;
 
#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(i, a) for (auto &i: (a))
#define sz(x) (int)(x).size()
#define all(v) (v).begin(), (v).end()
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)

void solve();

signed main () {
    clock_t beg = clock();
    cout << fixed << setprecision(15);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    #endif 
    int t = 1; 
    // cin >> t;    
    int tt = t;
    while (t--) {
        // cout << "Case #" << tt - t << ": "; 
        solve();
    }
    cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
    return 0;
}
const int N = 1e5 + 5;
int cnt[N] = {0};
int n;
int a[N];
void solve() {  
    cin >> n;
    int s = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ++cnt[a[i]];
        s += a[i];
    }
    int q;
    cin >> q;
    while (q--) {
        int b, c;
        cin >> b >> c;
        s += cnt[b] * (c - b);
        cnt[c] += cnt[b];
        cnt[b] = 0;
        cout << s << '\n';
    }
}       

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

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
};

int main() {
  int n, d, a;
  cin >> n >> d >> a;
  vector<P> p(n);
  rep(i,n) cin >> p[i].first >> p[i].second;
  sort(p.begin(), p.end());

  ll ans = 0;
  BIT<ll> bit(n+1);
  rep(i,n) {
    ll x = p[i].first;
    ll h = p[i].second;
    h -= bit.sum(i);
    if (h <= 0) continue;
    ll num = (h+a-1)/a;
    ans += num;
    ll damage = num*a;
    bit.add(i, damage);
    int rx = min(x+d*2, 1001001001ll);
    int j = upper_bound(p.begin(), p.end(), P(rx+1,-1)) - p.begin();
    bit.add(j, -damage);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
#define rep(i,a) for(int i = 0 ; i < a ; i ++)
int main(void){
  string str;
  int n,w,s,e;
  cin>>str;
  n = w = s = e = 0;
 
  rep(i,str.size()){
    if(str[i] == 'N')n=1;
    if(str[i] == 'W')w=1;
    if(str[i] == 'S')s=1;
    if(str[i] == 'E')e=1;
  }
  
  int judge = !(n ^ s) && !(w ^ e);
  

  cout<<(judge?"Yes":"No")<<endl;
}

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

const int N = 2e5 + 5;
typedef long long LL;

int n;
LL ans, a[N], cnt = N + 5;

int main() {
	cin>>n;
	for(int i = 1; i <= n; i++) 
		cin>>a[i];
	for(int i = n; i; i--) {
		if(a[i] < i - cnt + 1 && cnt <= i) {
			cout<<-1<<endl;
			return 0;
		}
		if(a[i] > i - 1) {
			cout<<-1<<endl;
			return 0;
		}
		if(a[i] == a[i + 1] - 1 || a[i] == 0) continue;
		ans += a[i];
		cnt = min(cnt, i - a[i] + 1);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
while 1:
    t = int(input())
    if t == 0:
        break
 
    n = int(input())
 
    ans = 0
    for _ in range(n):
        s, f = map(int, input().split())
        ans += f - s
 
    if ans >= t:
        print("OK")
    else:
        print(t - ans)


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

using namespace std;

#define sqr(x) ((x) * (x))
#define pb push_back
#define mp make_pair
#define ins insert
#define er erase
#define bg begin()
#define ed end()
#define f first
#define s second
#define fin(name) freopen(name, "r", stdin)
#define fout(name) freopen(name, "w", stdout)
#define files(name) fin(name".in"); fout(name".out")
#define enter cout << "\n"
#define space cout << " "
#define endl "\n"
#define fi(st,n) for (int i = (st); i <= (n); ++i)
#define fj(st,n) for (int j = (st); j <= (n); ++j)
#define fk(st,n) for (int k = (st); k <= (n); ++k)
#define fq(st,n) for (int q = (st); q <= (n); ++q)
#define fw(st,n) for (int w = (st); w <= (n); ++w)
#define ff(i, st, n) for (int (i) = (st); (i) <= (n); ++(i))
#define ei(st,n) for (int i = (st); i >= (n); --i)
#define ej(st,n) for (int j = (st); j >= (n); --j)
#define ek(st,n) for (int k = (st); k >= (n); --k)
#define ef(i, st, n) for (int (i) = (st); (i) >= (n); --(i))
#define ri(st,n) for (int i = (st); i < (n); ++i)
#define rj(st,n) for (int j = (st); j < (n); ++j)
#define rk(st,n) for (int k = (st); k < (n); ++k)
#define rq(st,n) for (int q = (st); q < (n); ++q)
#define rf(i, st, n) for (int (i) = (st); (i) < (n); ++(i))
#define clean(a) memset((a),0,sizeof (a))
#define sync ios_base::sync_with_stdio(0);cin.tie(0)
#define y1 dsklmlvmd

typedef long long ll;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ldbl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int inf = (int)1e9;
const dbl eps = (dbl) 1e-8;
const int mod = (int) 1e9 + 7;
const int maxn = (int) 1e5 + 5;
//const dbl M_PI = (dbl)2 * (dbl)acos(0);

//cout<<fixed<<setprecision(10);
//srand(time(0));

ll n, k, l, r, a, u, ans[1111], K;
vi ot;

void dzen(ll n) {
    if (n == 0)
        return;
    if (n & 1) {
        ++u;
        ot.pb(u);
        dzen((n - 1) / 2);
    } else {
        ++u;
        ot.pb(-u);
        dzen(n - 1);
    }
}

int main() {
//    fin("t.in");
    sync;
    cin >> n;
    l = 200;
    r = 200;
    u = 0;
    dzen(n);
    reverse(ot.begin(), ot.end());
    ri(0, ot.size()) {
        if (ot[i] < 0) {
            u = -ot[i];
            ans[--l] = u;
        } else {
            u = ot[i];
            ans[r++] = u;
        }
    }
//    cout << a << endl;
    cout << 2 * (r - l) << endl;
    ri(l, r) {
        cout << ans[i] << " ";
    }
    l = 200;
    r = 200;
    ri(0, ot.size()) {
        if (ot[i] < 0) {
            u = -ot[i];
            ans[r++] = u;
        } else {
            u = ot[i];
            ans[r++] = u;
        }
    }
    ri(l, r) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

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

using namespace std;

int main(){
  int n;
  cin >> n;
  
  vector<long long> a_p(n);
  for(int i = 0; i < n; ++i){
    long long in;
    cin >> in;
    a_p[i] = in - (long long)i - 1;
  }
  
  sort(a_p.begin(), a_p.end());
  
  long long sad = 0;
  
  long long b = a_p[n / 2];
  for(int i = 0; i < n; ++i){
    sad += abs(a_p[i] - b);
  }
  
  cout << sad << endl;
  
  return 0;
}

Measured memory_bytes: 1792
import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		Scanner sc=new Scanner(System.in);
		int roop;
		int t,n,e,s,w,b;
		int score;
		int[] dice=new int[6];
		String act;
		while((roop=sc.nextInt())!=0){
			score=1; t=1; n=5; b=6; s=2; e=3; w=4;	//初期状態
			for(int i=0;i<roop;i++){
				act=sc.next();
				if(act.equals("North")){
					dice=move(s,t,n,b,e,w);
				}else if(act.equals("East")){
					dice=move(w,n,e,s,t,b);
				}else if(act.equals("South")){
					dice=move(n,b,s,t,e,w);
				}else if(act.equals("West")){
					dice=move(e,n,w,s,b,t);
				}else if(act.equals("Right")){
					dice=move(t,w,b,e,n,s);
				}else if(act.equals("Left")){
					dice=move(t,e,b,w,s,n);
				}
				t=dice[0]; n=dice[1]; b=dice[2]; s=dice[3]; e=dice[4]; w=dice[5];
				score+=t;
			}
			System.out.println(score);
		}
		sc.close();
	}
	
	static int[] move(int t,int n,int b,int s,int e,int w){
		int[] dice=new int[6];
		dice[0]=t; dice[1]=n; dice[2]=b; dice[3]=s; dice[4]=e; dice[5]=w;
		return dice;
	}
}

Measured memory_bytes: 25332
#include<stdio.h>
int main()
{
	int n,k,d,a,i,j,c=0,f[101]={0};
	scanf("%d %d",&n,&k);
	for(i=0;i<k;i++){
		scanf("%d",&d);
		for(j=0;j<d;j++){
			scanf("%d",&a);
			f[a]=1;
		}
	}
	for(i=1;i<=n;i++){
		if(f[i]==0) c++;
	}
	printf("%d\n",c);
	return 0;
}


Measured memory_bytes: 1732
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
using namespace std;
const int mod=1e9+7;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n,m; cin >> n >> m;
    vector<bool> ok(n+1,true); 
    rep(i,0,m){
        int a; cin >> a;
        ok[a]=false;
    }
     vector<long long>dp(n+1,0);
     dp[0]=1;
     rep(i,1,n+1){
        if(ok[i-1]){
            dp[i]+=dp[i-1];
            dp[i]%=mod;
        }
        if(i>1 && ok[i-2]){
            dp[i]+=dp[i-2];
            dp[i]%=mod;
        }
     }

    cout << dp[n] << endl;
 }    


Measured memory_bytes: 1024
n = int(input())
arm = []
for _ in range(n):
    x, l = map(int,input().split())
    arm.append([x-l, x+l])
arm.sort(key=lambda x: x[1])
cnt = 0
pr = -float('inf')
for a in arm:
    if pr <= a[0]:
        cnt += 1
        pr = a[1]
print(cnt)


Measured memory_bytes: 25392
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const ll INF=1000000010;
const ll MOD=1000000007;
const ll LINF=4000000000000000000;
const long double EPS=1e-9;
typedef pair<int,int> P;
int main(){
    int n;cin>>n;
    int p[110];
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
    int ans=0;
    for(int i=1;i<=100;i++){
        int c=0;
        for(int j=0;j<n;j++){
            if(p[j]>=i){
                c++;
            }
        }
        if(c>=i){
            ans=i;
        }
    }
    cout<<ans<<endl;
}   



Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;} 
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



ll calc(ll n)
{
        if (n % 4 == 0) return n;
        else if (n % 4 == 1) return 1;
        else if (n % 4 == 2) return n + 1;
        else return 0;
}

int main()
{
        ll A, B;
        cin >> A >> B;
        ll ans = calc(B) ^ calc(A-1);
        cout << ans << endl;
}

// int main()
// {
//         ll A, B;
//         cin >> A >> B;
//         vll bits;
//         while(A and B) {
//                 if ((B - A)%2 == 0) bits.push_back(1);
//                 else bits.push_back(0);
//                 A/=2; B/=2;
//         }
//         print1d(bits);
// }

Measured memory_bytes: 3636
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

using i64=long long;
using vx=vector<i64>;
using vvx=vector<vx>;

i64 numways(const vx &cards, i64 ave) {
    int n=cards.size();
    i64 x=ave;
    vx y(n);

    for (int i=0; i<n; ++i) {
        y[i] = cards[i] - ave;
        if (x < cards[i])
            x = cards[i];
    }

    vvx dp(2, vx((n*x)<<1|1)); dp[0][n*x]=1;
    for (int j=1; j<=n; ++j)
        for (int t=0; t<=2*n*x; ++t)
            if (t-y[j-1]>=0 && t-y[j-1]<=2*n*x) {
                dp[j&1][t] = dp[(j&1)^1][t] + dp[(j&1)^1][t-y[j-1]];
            } else {
                dp[j&1][t] = dp[(j&1)^1][t];
            }

    return dp[n&1][n*x]-1LL;
}

int main() {
    int n;
    i64 a;
    scanf("%d %lld", &n, &a);

    vx x(n);
    for (int i=0; i<n; ++i)
        scanf("%lld", &x[i]);

    printf("%lld\n", numways(x, a));
    return 0;
}


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

int a[105000];

int main()
{
	int n, b2, b4, b24, b, flag = 0;
	b2 = b4 = b24 = b = 0;
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cin >> a[i];
		if(a[i]%4 == 0) 
		{
			b4++;
		}
		else
		{
			if(a[i]%2 == 0)
			{
				b2++;
				flag = 1;
			}
			else b++;
		}
	}
	if(b4 >= b+b2-1)
		cout << "Yes" << endl;
	else
	{
		if(flag&&b4>=b)
			cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

Measured memory_bytes: 640
// Author:: Mohammad Faisal
// BEGINNING WITH THE NAME OF ALMIGHTY GOD 
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b;
  cin >> a >> b;
  (a<=9 && b<=9) ? cout<<a*b : cout<<"-1";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MOD 1000000007
#define pb push_back
using namespace std;

bool a[1010][1010];
long long dp[1010][1010];

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

	for(int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			
			if (c == '.') a[i][j] = 0;
			else a[i][j] = 1;
		}

	
	int ii = 0;
	while (a[ii][0] == 0 && ii < n) dp[ii++][0] = 1;
	ii = 0;
	while (a[0][ii] == 0 && ii < m) dp[0][ii++] = 1;

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (a[i][j] == 0) dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
		}
	}

	cout << dp[n - 1][m - 1];

	return 0;
}

Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> b(n,-1);
    vector<int> a(n);
    rep(i,0,n) cin >> a[i];
    bool bad = false;
    for(int i=n-1; i>=0; --i) {
        int j = 0;
        int x = a[i];
        while(j<n) {
            if(b[j]!=-1) ++j;
            else {
                --x;
                if(x==0) {
                    b[j] = a[i];
                    break;
                }
                ++j;
            }
        }
        if(j==n) {
            bad = true;
            break;
        }
    }
    if(bad) cout << -1 << endl;
    else {
        rep(i,0,n) cout << b[i] << "\n";
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdlib.h>
#include <dirent.h>
using namespace std;
#define sp << " " << 
typedef vector<int> vi;
typedef vector<long int> vli;
typedef vector<long long int> vlli;
typedef long int li;
typedef long long int lli;
typedef vector<pair<int,int> > vpi;
typedef vector<pair<lli,lli> > vplli;
typedef unordered_map<int,int> ump;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> arr;
    for(int i=0;i<n;i++){
        int input;
        cin >> input;
        arr.push_back(input);
    }
    if(n==1){
        return 0;
    }
    if(k==1){
        int summ = 0;
        for(int i=1;i<n;i++){
            summ+=abs(arr[i]-arr[i-1]);
        }
        cout << summ << endl;
        return 0;

    }
    vector<int> dp(k, INT_MAX);
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(int i=2;i<n;i++){
        int val = INT_MAX;
        
        int limit = i-k<0?0:i-k;
        // for(int val : dp){
        //     cout << val << " ";
        // }
        // cout << " DP " << endl;
        for(int j=i-1;j>=limit;j--){
            val = min(val,dp[j%k]+abs(arr[i]-arr[j]));
            // cout << i << " " << j << " " << val << endl;
        }
        dp[i%k]=val;
    }
    // for(int val : dp){
    //     cout << val << " ";
    // }
    // cout << endl;
    cout << dp[(n-1)%k] << endl;


    return 0;
}

// 6 10
// 3 4 2 5 1 2

Measured memory_bytes: 892
import java.util.Scanner;

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


Measured memory_bytes: 60172
fun main(args: Array<String>) {
    val s = readLine()!!
    val k = readLine()!!.toLong()

    if (s.first() != '1') {
        println(s.first())
        return
    }

    val len = s.takeWhile { it == '1' }.length
    if (k <= len) {
        println("1")
        return
    }

    val ans = s.dropWhile { it == '1' }.first()
    println(ans)
}

Measured memory_bytes: 33532
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
int N;
long long int ans=0;
map<int,int> m;
int main(){
  cin >> N;
  for(int i=0;i<N;i++){
    int x;
    cin >> x;
    m[x]++;
  }
  map<int,int>::iterator it;
  for(it=m.begin();it!=m.end();it++){
    if(it->second>it->first)ans+=(it->second-it->first);
    else if(it->second<it->first)ans+=it->second;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4736
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    public static int DistanceToRect(int A, int B, int C, int D, int x, int y)
    {
        var xDist = 0;
        var yDist = 0;
        if (x < A)
        {
            xDist = A - x;
        }
        else if (C < x)
        {
            xDist = x - C;
        }

        if (y < B)
        {
            yDist = B - y;
        }
        else if (D < y)
        {
            yDist = y - D;
        }
        return xDist + yDist;
    }

    public static void Main()
    {
        while (true)
        {
            var N = int.Parse(Console.ReadLine());
            if (N == 0)
            {
                break;
            }
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var A = input[0];
            var B = input[1];
            var C = input[2];
            var D = input[3];
            var x = new int[N + 1];
            var y = new int[N + 1];
            for (int i = 0; i < N + 1; i++)
            {
                var input2 = Console.ReadLine().Split().Select(int.Parse).ToArray();
                x[i] = input2[0];
                y[i] = input2[1];
            }
            var ans = 0;
            for (int i = 0; i < N; i++)
            {
                var dist1 = Math.Max(DistanceToRect(A, B, C, D, x[i], y[i]) - 1, 0) + DistanceToRect(A, B, C, D, x[i + 1], y[i + 1]);
                var dist2 = Math.Abs(x[i] - x[i + 1]) + Math.Abs(y[i] - y[i + 1]);
                ans += Math.Min(dist1, dist2);
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 16252
#include <iostream>

#define ll long long int
using namespace std;

ll mod = 1000000007;

ll factorials[1000005];
ll inv[1000005];
ll dp[1000005];

ll mod_pow(ll k, ll pow) {
  ll ans = 1;
  while (pow > 0) {
    if (pow & 1) ans = ans * k % mod;
    k = k * k % mod;
    pow >>= 1;
  }
  return ans;
}

int main() {
  ll n;
  cin >> n;
  factorials[0] = 1;
  inv[0] = 1;

  for (int i = 1; i < 1000005; i++) {
    factorials[i] = (factorials[i - 1] * i) % mod;
    inv[i] = (inv[i - 1] * mod_pow(i, mod - 2)) % mod;
  }
  
  ll min_score = (n + 1) / 2;
  ll max_score = n - 1;
  ll ans = 0;
  ll prev = 0;
  for (int i = min_score; i <= max_score; i++) {
    ll cnk = ((factorials[i - 1] * inv[n - 1 - i] % mod) * inv[2 * i - n] % mod) % mod;
    ll add = (cnk * factorials[i] % mod) * factorials[n - 1 - i] % mod;
    ans = (ans + (((add - prev + mod) % mod) * i) % mod) % mod;
    prev = add;
  }
  cout << ans;
}


Measured memory_bytes: 17536
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//??\?????¨
		int n = Integer.parseInt(br.readLine());

		int[] price = new int[n];
		for(int i = 0; i < n; i++){
			price[i] = Integer.parseInt(br.readLine());
		}

		int maxProfit = Integer.MIN_VALUE;
		int prevBuy = Integer.MAX_VALUE;

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

			if(price[i] >= prevBuy){
				continue;
			}
			prevBuy = price[i];
			
			for(int j = i + 1; j < n; j++){
				if(price[j] > tmpHigh){
					tmpHigh = price[j];
				}
			}

			if(tmpHigh - price[i] > maxProfit){
				maxProfit = tmpHigh - price[i];
			}
		}


		System.out.println(maxProfit);

	}

}

Measured memory_bytes: 42768
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

#define ll long long

#ifndef ONLINE_JUDGE
#define debug(format, ...) fprintf(stderr, \
    "%s:%d: " format "\n", __func__, __LINE__,##__VA_ARGS__)
#else
#define debug(format, ...)
#define NDEBUG
#endif

struct Edge {
    int to, wt;
};

vector<Edge> graph[100005];

int uf[100005];
bool bfsvis[100005][3];
int compcnt[100005][3];
int indeg[100005], outdeg[100005];
bool interesting[100005];
int ecnt[100005];

int fin(int a)
{
    if (uf[a] == a) return a;
    return uf[a] = fin(uf[a]);
}

void un(int a, int b)
{
    a = fin(a); b = fin(b);
    if (a == b) return;
    uf[a] = b;
}

int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) uf[i] = i;
    vector<int> eend;
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        Edge e; e.to = v; e.wt = 1;
        graph[u].push_back(e);
        e.to = u; e.wt = 2;
        graph[v].push_back(e);
        indeg[v]++; outdeg[u]++;
        eend.push_back(u);
        un(u, v);
    }
    for (int i = 0; i < m; i++) {
        ecnt[fin(eend[i])]++;
    }
    for (int i = 1; i <= n; i++) {
        if (indeg[i] && outdeg[i]) {
            interesting[fin(i)] = true;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (fin(i) != i) continue;
        queue<pair<int, int> > bfs;
        bfs.push(make_pair(i, 0));
        bfsvis[i][0] = true;
        while (!bfs.empty()) {
            pair<int, int> cur = bfs.front();
            bfs.pop();
            for (int j = 0; j < graph[cur.first].size(); j++) {
                int nxt = graph[cur.first][j].to;
                int nxtwt = (cur.second + graph[cur.first][j].wt) % 3;
                if (bfsvis[nxt][nxtwt]) continue;
                bfsvis[nxt][nxtwt] = true;
                bfs.push(make_pair(nxt, nxtwt));
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            if (bfsvis[i][j]) {
                compcnt[fin(i)][j]++;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (fin(i) != i) continue;
        if (!interesting[i]) {
            ans += (ll)ecnt[i];
            continue;
        }
        if (bfsvis[i][0] && bfsvis[i][1]) {
            ans += (ll)compcnt[i][0] * (ll)compcnt[i][0];
        } else {
            for (int j = 0; j < 3; j++) {
                ans += (ll)compcnt[i][j] * (ll)compcnt[i][(j + 1) % 3];
            }
        }
    }
    printf("%lld", ans);
    return 0;
}


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

int N,M,L;
long INF=1e15;
long d[500][500],e[500][500];
int Q;
void wf1(int N){
  for(int k=0;k<N;k++){
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }
}

void wf2(int N){
  for(int k=0;k<N;k++){
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
      }
    }
  }
}

int main() {
  cin >>N>>M>>L;
  // 繋がってない街間のコストはINF、繋がっているならcを代入
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++) d[i][j]=INF;
  }
  for(int i=0;i<M;i++){
    int a,b,c;
    cin>>a>>b>>c;
    d[a-1][b-1]=c;
    d[b-1][a-1]=c;
  }
  // ワーシャルフロイド1回目街間の最小コストを求める
  wf1(N);
  // 街間のコストがL以下なら補給回数1を代入
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++) {
      if(d[i][j]<=L) e[i][j]=1;
      else e[i][j]=INF;
    }
  }
  wf2(N);

  cin>>Q;
  for(int i=0;i<Q;i++){
    int s,t;
    cin>>s>>t;
    // 最初はタンクはいっぱいなので1を引く
    if(e[s-1][t-1]<INF) cout<<e[s-1][t-1]-1<<endl;
    else cout<<-1<<endl;
  }
}


Measured memory_bytes: 2816
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define pii std::pair<int,int>
#define pli std::pair<ll,int>
#define pil std::pair<int,ll>
#define psi std::pair<string,int>
#define pll std::pair<ll,ll>
#define pci std::pair<char,int>
#define sll(x) scanf("%lld",&x)
#define prll(x) printf("%lld ",x)
#define pri(x) printf("%d ",x)
#define si(x) scanf("%d",&x)
#define pb push_back
#define vll std::vector<ll>
#define vpi std::vector<std::pair<int,int>>
#define vi std::vector<int>
#define vvi std::vector<std::vector<int>>
#define vvpil std::vector<std::vector<std::pair<int,ll>>>
#define vlpii std::vector<std::list<pii>>
#define vlpil std::vector<std::list<pil>>
#define li std::list<int>
#define lpil std::list<pil>
#define Endl printf("\n")
#define vli vector<list<int>>
#define vvll vector<vector<ll>>
#define mp make_pair
#define x first
#define y second
#define ull uint64_t
#define ma 100000000
#define imie(...) "[" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
const ll  INF=10000000000000;
const ll mod =  1e9 + 7;
using namespace std;
void add(ll& a , ll b){
	a += b;
	if(a >= mod) a -= mod;
}
ll mul(ll a , ll b){
	return (a * b) % mod;
}
ll Pow(ll a , ll b){
	if(b == 0) return 1 ;
	ll c = Pow(a , b / 2) ;
	if(b % 2) return (a * ((c * c)% mod )) % mod ;
	return (c * c) % mod ;
}
//check modulo
int main(){
	IOS;
	cout.precision(30) ;
	ll d , g ;cin >> d >> g ;
	vector<vll> a(d) ;
	vll p(d) , c(d) ;for(int i = 0 ; i < d ; i++) {cin >> p[i] >> c[i] ;a[i] = {p[i] , c[i] , i + 1} ;}
	sort(a.begin() , a.end()) ;
	ll ans = 1e9 ;
	do{
		ll sum = 0 ,tmp = 0 ;
		for(int i = 0 ; i < d ; i++){
			if(sum + 100 * a[i][2] * a[i][0] + a[i][1] >= g){
				if(sum + 100 * a[i][2] * a[i][0] >= g){
					ll diff = g - sum ;
					tmp += ceil((long double)diff / (a[i][2] * 100)) ;
				}
				else{
					tmp += a[i][0] ;
				}
				break ;
			}
			else{
				tmp += a[i][0] ;
				sum +=  100 * a[i][2] * a[i][0] + a[i][1] ;
			}
		}
		ans = min(ans , tmp) ;
	}while(next_permutation(a.begin() , a.end())) ;
	cout << ans << endl; 		
	return 0;
}


Measured memory_bytes: 256
# ABC137 D
import heapq

N,M=map(int,input().split())
AB=[]
for _ in [0]*N:
    a,b=map(int,input().split())
    AB.append((-a,-b))
AB.sort()
AB=[(-a,-b) for a,b in AB]

res=0
num=0
work=[]
hard=[0]*(M+1)
for a,b in AB:
    #a日後のしごとの話をしている→M-a+1件まで受注可能
    if num<M-a+1:
        # 仕事に余裕はある
        heapq.heappush(work,(b,a))
        hard[a]+=1
        res+=b
        num+=1
    else:
        # 仕事は十分持っている
        heapq.heappush(work,(b,a))
        c,d=heapq.heappop(work)
        res+=b-c
print(res)

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

int main(){
  ll N,count=0;
  cin >> N;
  vector<ll> a(N+1),b(N);
  for(int i=0;i<N+1;i++){
  	cin >> a.at(i);
  }
  for(int i=0;i<N;i++){
  	cin >> b.at(i);
  }
  for(int i=0;i<N;i++){
  	if(b.at(i)-a.at(i)<=0){
    	count+=b.at(i);
    }else if(a.at(i)+a.at(i+1)>=b.at(i)){
      	count+=b.at(i);
    	a.at(i+1)-=b.at(i)-a.at(i);
    }else if(a.at(i)+a.at(i+1)<b.at(i)){
    	count+=a.at(i);
        count+=a.at(i+1);
      	a.at(i+1)=0;
    }
  }
 
  cout << count;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC063C
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] s = new int[N];
            int sum = 0;
            for(int i=0; i < N; i++)
            {
                s[i] = int.Parse(Console.ReadLine());
                sum += s[i];
            }
            Array.Sort(s);

            if(sum % 10 > 0)
            {
                Console.WriteLine(sum);
            }
            else
            {
                for(int i=0; i < N; i++)
                {
                    if(s[i] % 10 > 0)
                    {
                        Console.WriteLine(sum - s[i]);
                        return;
                    }

                }

                Console.WriteLine(0);
            }

        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <iomanip>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <ctime>
#include <fstream>
#include <stdarg.h>
using namespace std;
const bool debug=false;
const bool INJUDGE=false;
#define FASTERCIN cin.tie(0);ios_base::sync_with_stdio(false)
typedef long long ll;
/*Time:
Status:
Type:
Author:*/
template<class T>T emax(T& a,T b){return a=max(a,b);}
template<class T>T emin(T& a,T b){return a=min(a,b);}
template<class T>void byebye(T info){cout<<info<<endl;exit(0);}
int n,k; 
ll ans;
int main(){
	cin>>n>>k;
	ll tmp=n/k;
	if(k&1){
		cout<<(tmp*tmp*tmp)<<endl;
	}
	else{
		ll tmp2=n/k+(n%k>=k/2);
		cout<<(tmp*tmp*tmp)+(tmp2*tmp2*tmp2)<<endl;
	}
	//cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long ,long long>pll;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
ll lcm(ll a, ll b) {return ((a*b)/gcd(a,b));}
bool cmp(int a,int b){return a>b;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

unsigned long long modpow(unsigned long long n, unsigned long long k, unsigned long long mod)
{
if (k == 0) return 1;
long long r = modpow(n * n % mod, k >> 1, mod);
if (k & 1) r = r * n % mod;
return r;
}

void solve(){
    int n;cin >> n;
    vector<ll>a(n);
    for(int i = 0;i<n;i++) cin >> a[i];
    vector<vector<ll>>dp(n,vector<ll>(n,0));
    for(int i = 0;i<n;i++) dp[i][i] = a[i];
    for(int i = 1;i<n;i++){
        for(int j = 0;i+j<n;j++){
            dp[j][i+j] = max(a[j]-dp[j+1][i+j],a[i+j]-dp[j][i+j-1]);
        }
    }
    cout << dp[0][n-1];
}

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

Measured memory_bytes: 73656
// C - String Transformation
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

string S, T;
int n;
vector<int> start(26, -1);
vector<int> terminal(26, -1);

int main(){
	cin>>S>>T;
	n = S.size();
	rp(i, 0, n){
		int s = S[i]-'a';
		int t = T[i]-'a';
		if(start[s] > -1 || terminal[t] > -1){
			if(start[s] != t || terminal[t] != s){
				puts("No");
				return 0;
			}
		}
		else{
			start[s] = t;
			terminal[t] = s;
		}
	}
	puts("Yes");
}


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

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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

constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
//constexpr int INF = 1001001001;
constexpr ll INF = 1001001001001001001ll;
constexpr double EPS = 1e-10;
using number = long long;




inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}

inline ll mul(ll a, ll b, ll m) {
    a = mod(a, m); b = mod(b, m);
    if (b == 0) return 0;
    ll res = mul(mod(a + a, m), b >> 1, m);
    if (b & 1) res = mod(res + a, m);
    return res;
}

ll pow(ll a, ll n, ll m) {
    if (n == 0) return 1 % m;
    ll t = pow(a, n / 2, m);
    t = mul(t, t, m);
    if (n & 1) t = mul(t, a, m);
    return t;
}

/*
vector<pair<ll, ll> > prime_factor(ll n) {
    vector<pair<ll, ll> > res;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int exp = 0;
            while (n % i == 0) {
                ++exp;
                n /= i;
            }
            res.push_back(make_pair(i, exp));
        }
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}*/
number euler_phi(number n) {
    number ret = n;
    for (number i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ret -= ret / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ret -= ret / n;
    return ret;
}

number GCD(number a, number b) { return b != 0 ? GCD(b, a % b) : a;}
number LCM(number a, number b) { return a * (b / GCD(a, b)); }


const ll L = 50;
ll solve(ll A, ll M) {
    if (A == 0) return M;
    if (A == 1) return 1;
    if (M == 1) return L;
    ll phiM = euler_phi(M);
    /*vector<pair<ll, ll> > divM = prime_factor(M);
    for (int i = 0; i < divM.size(); ++i) {
        ll p = divM[i].first;
        phiM *= p - 1;
        phiM /= p;
    }*/
    ll y = solve(A, phiM);
    ll lcm = LCM(phiM, M);
    ll res = pow(A, y, lcm);
    while (res < L) res += lcm;
    return res;
}

int main() {
    int Q; cin >> Q;

    rep(i, Q) {
        ll a, m; cin >> a >> m;
        ll res = solve(a, m);
        cout << res << endl;
    }
}

Measured memory_bytes: 256
#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 next = 1;
    int cnt = 0;
    for(int i=0;i<N;i++){
        if (A[i] == next){
            next++;
        }else{
            cnt++;
        }
    }
    cout << ((cnt == N) ? -1 : cnt) << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <map>
#include <algorithm>

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

using namespace std;

int n, m;
int u[1000];

int find(int i){
  return u[i] == i ? i : u[i] = find(u[i]);
}
void unite(int a, int b){
  u[find(a)] = find(b);
}

int main(){
  cin >> n >> m;
  rep(i, n){
    u[i] = i;
  }
  rep(i, m){
    int a, b;
    cin >> a >> b;
    unite(a - 1, b - 1);
  }
  map<int, int> x;
  rep(i, n){
    ++x[find(i)];
  }
  int p = 0;
  for(auto& v: x){
    if(v.second > 1){
      ++p;
    }
    else{
      --p;
    }
  }
  cout << abs(p) << endl;
  return 0;
}

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

using namespace std;
using ll = long long;

#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define RS(N) resize(N)
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);
#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);

#define MOD 1000000007

void init();
void solve();

signed main()
{
	init();
	solve();
}

int N;
vector<int> a;

void init()
{
	cin >> N;
	CINV(a, N);
	rep(i, N) {
		a[i] *= N;
	}
}

void solve()
{
	int ave = 0;
	rep(i, N) {
		ave += a[i] / N;
	}
	int mi = 1000000;
	rep(i, N) {
		a[i] = abs(a[i] - ave);
		mi = min(a[i], mi);
	}
	rep(i, N) {
		if (a[i] == mi) {
			cout << i << endl;
			return;
		}
	}
}






Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int a, b, c, d; cin >> a >> b >> c >> d;
	if (a + b < c + d)cout << "Right" << endl;
	else if (a + b > c + d)cout << "Left" << endl;
	else cout << "Balanced" << endl;
	return 0;
}

Measured memory_bytes: 3584
n, T = map(int, input().split())

index = -1
min_c = 9999
for i in range(n):
    c, t = map(int, input().split())
    # print(f'{c} {t}')
    
    if t <= T and min_c > c:
        index = i + 1
        min_c = c
    # print(min_c)
        
if index == -1:
    print('TLE')
else:
    print(min_c)

Measured memory_bytes: 9072
#include<iostream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<math.h>
#define EPS1 1e-6
#define EPS2 1e-9
#define EPS3 1e-15
#define fi first
#define se second
#define ff first.first
#define ss second.second
#define sf second.first
#define fs first.second
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ul;
typedef pair<ld,ld> ldd;
typedef pair<double,double> dd;
typedef pair<int,int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef pair<ld,ii> dii;

int a[100100];
int main(){
	int n;
	cin>>n;
	for(int i = 0;i<n;i++) cin>>a[i];
	int ans = 0,ct = 0;
	for(int i = 0;i<n-1;i++){
//		cout<<ct<<"\n";
		if(a[i+1] > a[i] ) {
			ans = max(ans,ct);
			ct = 0;	
		}else ct++;
	}
	ans = max(ans,ct);
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
const int MOD = 1e9 + 7;

ll N, M, K, Q, W, H, L, R, C;
string S;

int main() {
    int mod = 2019;
    int L, R;
    cin >> L >> R;
    /*
    auto m = make_vec<int>(mod + 1, mod + 1);
    for (int i = 0; i < mod; i++) {
        for (int j = 0; j < mod; j++) {
            m[i][j] = i * j % mod;
        }
    }
    */
    int ans = INF;
    for (int i = L; i <= R - 1 && i < L + mod; i++) {
        for (int j = i + 1; j <= R && j < i + 1 + mod; j++) {
            chmin(ans, (i % mod) * (j % mod) % mod);
        }
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int mod = 1e9 + 7;

struct matrix
{
	int a[2][2];
	matrix operator * (matrix that) 
	{
		matrix ans;
		memset(ans.a, 0, sizeof ans.a);
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				for (int k = 0; k < 2; ++k)
					ans.a[i][j] = (ans.a[i][j] + 1LL * a[i][k] * that.a[k][j]) % mod;
		return ans;
	}
} w;

int fpow(int a, long long x)
{
	int ret = 1;
	for (; x; x >>= 1)
	{
		if (x & 1) ret = 1LL * ret * a % mod;
		a = 1LL * a * a % mod;
	}
	return ret;
}

matrix fpow(matrix a, long long x)
{
	matrix ret;
	memset(ret.a, 0, sizeof ret.a);
	ret.a[0][0] = ret.a[1][1] = 1;
	for (; x; x >>= 1)
	{
		if (x & 1) ret = ret * a;
		a = a * a;
	}
	return ret;
}

int H, W;

long long K;

char str[1010][1010];

int main()
{
	scanf("%d%d%lld", &H, &W, &K);
	for (int i = 1; i <= H; ++i)
		scanf("%s", str[i] + 1);
	int cntH = 0, cntW = 0;
	for (int i = 1; i <= H; ++i)
		if (str[i][1] == str[i][W] && str[i][1] == '#') ++cntH;
	for (int i = 1; i <= W; ++i)
		if (str[1][i] == str[H][i] && str[1][i] == '#') ++cntW;
	int cnt = 0;
	for (int i = 1; i <= H; ++i)
		for (int j = 1; j <= W; ++j)
			if (str[i][j] == '#') ++cnt;
	if (!cntH && !cntW)
	{
		printf("%d\n", fpow(cnt, K - 1));
		return 0;
	}
	if ((cntH && cntW) || !K)
	{
		puts("1");
		return 0;
	}
	if (cntH)
	{
		w.a[0][0] = cnt;
		for (int i = 1; i <= H; ++i)
			for (int j = 1; j < W; ++j)
				if (str[i][j] == '#' && str[i][j + 1] == '#')
					++w.a[0][1];
		w.a[1][1] = cntH;
	}
	else
	{
		w.a[0][0] = cnt;
		for (int i = 1; i < H; ++i)
			for (int j = 1; j <= W; ++j)
				if (str[i][j] == '#' && str[i + 1][j] == '#')
					++w.a[0][1];
		w.a[1][1] = cntW;
	}
	w = fpow(w, K - 1);
	printf("%d\n", (w.a[0][0] - w.a[0][1] + mod) % mod);
	return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll MOD = 1000000007;
const ll N=1e5+9;
int main()
{
    FASTINOUT;
    string s;
    cin>>s;
    int ls=s.length();
    if (ls%2)
        cout<<"No\n";
    else{
        for (int i=1;i<ls;i+=2){
            if (s[i]=='i'&&s[i-1]=='h')
                continue;
            else
            {
                cout<<"No\n";
                return 0;
            }
        }
        cout<<"Yes\n";
    }
    return 0;
}


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

vector<bool> processed;
vector<int> topologicalsort;

void topsort(int v, vector<int> adjlist[])
{
    processed[v]=true;
    for (int q : adjlist[v])
    {
        if (!processed[q])
        {
            topsort(q, adjlist);
        }
    }
    topologicalsort.push_back(v);
}

int main()
{
    int n,m;
    cin >> n >> m;
    for (int q = 0; q < n; q++)
    {
        processed.push_back(false);
    }
    vector<int> adjlistforward[n];
    vector<int> adjlistbackward[n];
    for (int q = 0; q < m; q++)
    {
        int a,b;
        cin >> a >> b;
        adjlistforward[a-1].push_back(b-1);
        adjlistbackward[b-1].push_back(a-1);
    }
    for (int q = 0; q < n; q++)
    {
        if (processed[q]==false && adjlistbackward[q].size()==0)
        {
            topsort(q, adjlistforward);
        }
    }
    vector<int> actualsort;
    for (int q = n-1; q >= 0; q--)
    {
        actualsort.push_back(topologicalsort[q]);
    }
    int maxlengths[n];
    int maxx = 0;
    for (int q = 0; q < n; q++)
    {
        //cout << actualsort[q] << endl;
        maxlengths[actualsort[q]]=0;
        for (int w : adjlistbackward[actualsort[q]])
        {
            maxlengths[actualsort[q]] = max(maxlengths[actualsort[q]], maxlengths[w]+1);
            maxx = max(maxx, maxlengths[actualsort[q]]);
        }
    }
    cout << maxx;
    return 0;
}


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

int main(){
  int N,M,D[200000],T[200000];
  cin >> N;
  for(int i=0; i<N; i++) cin >> D[i];
  cin >> M;
  for(int i=0; i<M; i++) cin >> T[i];
  sort(D,D+N);
  sort(T,T+M);
  int pos=0;
  bool check;
  for(int i=0; i<M; i++){
    check=false;
    while(pos<N){
      if(D[pos]==T[i]){
        pos++;
        check=true;
        break;
      }else{
        pos++;
      }
    }
    if(check==false) break;
  }
  cout << ((check==true)?"YES":"NO") << endl;
}

Measured memory_bytes: 1792
using System;

namespace AOJ {
    class ALDS1_2_B {
        static void Main(string[] args) {
            int n = int.Parse(Console.ReadLine());
            string[] input = Console.ReadLine().Split();
            int[] data = new int[n];
            for (int i = 0; i < input.Length; i++) {
                data[i] = int.Parse(input[i]);
            }
            SelectionSort(data, n);
        }

        static void SelectionSort(int[] A, int n) {
            int count = 0;
            for(int i = 0; i < n-1; i++) {
                int minindex = i;
                for(int j = i; j < n; j++) {
                    if (A[j] < A[minindex]) minindex = j;
                }
                int tmp = A[i];
                A[i] = A[minindex];
                A[minindex] = tmp;
                if(i!=minindex)count++;
            }
            for (int i = 0; i < n; i++) {
                if (i != n - 1) Console.Write(A[i] + " ");
                else Console.WriteLine(A[i]);
            }
            Console.WriteLine(count);
        }
    }
}



Measured memory_bytes: 18008
/*
　　　∫ ∫ ∫
　　　ノヽ
　　（＿　 ）
　（＿　　　 ）
（＿＿＿＿＿＿ ）
　ヽ(´･ω･)ﾉ　
　　 |　 /
　　 UU
*/
#pragma region macro
#include <bits/stdc++.h>
typedef long long int64;
using namespace std;
typedef vector<int> vi;
const int MOD = (int)1e9 + 7;
const int64 INF = 1LL << 62;
const int inf = 1<<30;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,s,n) for (int i = s; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
#define mp make_pair
#define bn '\n'
template <typename T>
ostream& operator<<(ostream& os, const vector<T> &V){
    int N = V.size();
    REP(i,N){
        os << V[i];
        if (i!=N-1) os << " ";
    }
    os << "\n";
    return os;
}
template <typename T,typename S>
ostream& operator<<(ostream& os, pair<T,S> const&P){
    os << "(";
    os << P.first;
    os << " , ";
    os << P.second;
    os << ")";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T> &S){
    auto it=S.begin();
    while(it!=S.end()){
        os << *it;
        os << " ";
        it++;
    }
    os << "\n";
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, deque<T> &q){
    for(auto it=q.begin();it<q.end();it++){
        os<<*it;
        os<<" ";
    }
    os<<endl;
    return os;
}
template <typename T,typename S>
ostream& operator<<(ostream& os, map<T,S> const&M){
    for(auto e:M){
        os<<e;
    }
    os<<endl;
    return os;
}
vector<pair<int,int>> dxdy = {mp(0,1),mp(1,0),mp(-1,0),mp(0,-1)};
#pragma endregion
//fixed<<setprecision(10)<<ans<<endl;



int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int64 N,S;
    cin >> N >> S;
    vector<int64> A(N);
    REP(i,N) cin >> A[i];

    int l = 0; int64 now = 0;
    int ans = N+1;
    REP(r,N){
        now += A[r];
        if(now < S) continue;
        while(now - A[l]>=S) now-=A[l++];
        chmin(ans,r-l+1);
    }

    if(ans==N+1)cout << 0 << bn;
    else cout << ans << endl;
}


Measured memory_bytes: 3632
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    D = int(input())
    c = list(map(int, input().split()))
    s = [None for _ in range(D)]
    for i in range(D):
        s[i] = list(map(int, input().split()))
    # 単純にもっともsの大きいのを選択
    for i in range(D):
        print(s[i].index(max(s[i]))+1)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9828