akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100005;

int a[maxn];

int gcd(int x,int y){
  return y==0?x:gcd(y,x%y);
}

int main() {
   // freopen("in.cpp","r",stdin);
    int n,K;
    cin>>n>>K;
    for(int i=0;i<n;i++)cin>>a[i];
    int tt=a[0];
    for(int i=1;i<n;i++){
      tt=gcd(a[i],tt);
    }
    bool sign=0;
    for(int i=0;i<n;i++)if(a[i]>=K&&(a[i]-K)%tt==0)sign=1;
    if(sign)cout<<"POSSIBLE"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
    return 0;
}


Measured memory_bytes: 640
N = gets.to_i
ary = gets.split.map(&:to_i)
hash = {}
ary.each do |n|
    hash[n-1] = hash[n-1].to_i + 1
    hash[n] = hash[n].to_i + 1
    hash[n+1] = hash[n+1].to_i + 1
end
puts hash.max{|a, b| a[1]<=>b[1]}[1]

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

#define debug(args...) \
cout << "#" << __LINE__ << ": "; \
__dbg(split(#args, ',').begin(), args);
vector<string> split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c))
		v.emplace_back(x);
	return move(v);
}
template<typename T, typename... Args>
inline string to_str(T x) {
	stringstream ss; ss << "[";
	for (auto it = x.begin(); it != x.end(); it++) {
		if (it != x.begin()) ss << " ";
		ss << (*it);
	}
	ss << "]";
	return ss.str();
}
template<typename T, typename... Args>
inline string to_str(stack<T> x) {
	stringstream ss; ss << "[";
	bool first = 1;
	while (!x.empty()) {
		if (!first)
			ss << " ";
		ss << x.top();
		x.pop();
		first = 0;
	}
	ss << "]";
	return ss.str();
}
template<typename T> inline void __dbg_var(vector<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(list<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(set<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(unordered_set<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(stack<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(T val) { cout << val; }
inline void __dbg(vector<string>::iterator it) { cout << endl; }
template<typename T, typename... Args>
inline void __dbg(vector<string>::iterator it, T a, Args... args) {
	cout << it->substr((*it)[0] == ' ', it->length()) << "=";
	__dbg_var(a);
	cout << " ";
	__dbg(++it, args...);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a, b, c, d;
	bool plays = true;
	cin >> a >> b >> c >> d;
	
	
	while (a>0 && c>0) {
		if (plays)
			c-=b;
		else a-=d;
		plays=!plays;
	}
	if (a>0)
		cout << "Yes\n";
	else cout << "No\n";
	return 0;
}



Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int arr[101], M, N, cnt = 0, votes = 0;
int main(){
  cin >> N >> M;
  for (int i = 1; i<=N; i++){
    cin >> arr[i];
    votes += arr[i];
  }
  double thresh = (double)votes/((double) M*4);
  for (int i = 1; i<=N; i++){
    if ((double)arr[i] >= thresh)cnt++;
  }
  if (cnt >= M) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int N;
int A[100001];
int main(){
  int i, res=0;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<(N);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);A[Lj4PdHRW] += (-1);
    }
  }
  for(i=0;i<(N);i++){
    if(A[i]==i){
      res++;
      A[i+1] = -1;
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190822-2

// --- original code ---
// int N, A[100001];
// {
//   int i, res = 0;
//   rd(N,(A--)(N));
//   rep(i,N){
//     if(A[i]==i) res++, A[i+1] = -1;
//   }
//   wt(res);
// }


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
typedef long long ll;

int main(){
    int n,m,Q;
    cin >> n >> m >> Q;
    int dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<m;i++){
        int l,r;
        cin >> l >> r;
        dp[l][r]++;
    }

    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=n;j++){
            dp[i][j] += dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
        }
    }

    while(Q--){
        int p,q;
        cin >> p >> q;
        cout << dp[p][q] << endl;
    }
}

Measured memory_bytes: 1920
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int k = sc.nextInt();
        char[][] c = new char[h][w];
        for (int i = 0; i < h; i++) {
            String s = sc.next();
            c[i] = s.toCharArray();
        }
        int ans=0;
        for (int i = 0; i < (1 << h); i++) {
            for (int j = 0; j < (1 << w); j++) {
                int black = 0;
                for (int y = 0; y < h; y++) {
                    for (int x = 0; x < w; x++) {
                        if (((i >> y) & 1) == 0 && ((j >> x) & 1) == 0 && c[y][x] == '#') {
                            black++;
                        }
                    }
                }
                if (black == k){
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }

}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N, M;
vector< pair<ll, ll> > AB;

signed main()
{
    cin >> N >> M;
    REP(i, N) {
        ll a, b;
        cin >> a >> b;
        AB.push_back(make_pair(a, b));
    }
    SORT(AB);
    ll ans = 0;
    ll buy = 0;
    REP(i, N) {
        if(buy >= M) { break; }
        if(M - buy < AB[i].second) {
            ans += AB[i].first * (M - buy);
            buy += (M - buy);
        }
        else {
            ans += AB[i].first * AB[i].second;
            buy += AB[i].second;
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 2420
#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>;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> A(n, vector<int>(n-1));
    rep(i, n) {
        rep(j, n-1) {
            cin >> A[i][j];
            A[i][j]--;
        }
        reverse(A[i].begin(), A[i].end());
    }
    vector<P> p;
    auto check = [&](int i) {
        if (!A[i].size()) return;
        int j = A[i].back();
        if (A[j].back()==i) {
            if (i > j) swap(i, j);
            p.push_back(make_pair(i, j));
        }
    };
    rep(i, n) check(i);
    int day = 0;
    while(!p.empty()) {
        day++;
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        vector<P> q;
        swap(p, q);
        for (P m : q) {
            A[m.first].pop_back();
            A[m.second].pop_back();
        }
        for (P m : q) {
            check(m.first);
            check(m.second);
        }
    }
    bool flg = true;
    rep(i, n) {
        if (A[i].size()) {
            flg = false;
        }
    }
    if (flg) cout << day << endl;
    else cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 4224
import sys
import numpy as np
#import math
#import itertools
#import re
#from functools import lru_cache
from collections import deque

input = sys.stdin.readline
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    n, m = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(m)]
    graph = [[] for _ in range(n)]
    for a, b in AB:
        graph[a-1].append(b)
        graph[b-1].append(a)
    dist = np.ones(n)
    dist *= -1
    dist[0] = 0
    queue = deque([1])
    while queue:
        p = queue.popleft()
        for next in graph[p-1]:
            if dist[next-1] == -1:
                dist[next-1] = p
                queue.append(next)

    if np.count_nonzero(dist == -1) > 0:
        print(c)
    else:
        print('Yes')
        for d in dist[1:]:
            print(int(d))


if __name__ == '__main__':
    main()


Measured memory_bytes: 75476
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <iostream>
#include <algorithm>
using namespace std;

const int mod = 1e9 + 7;

long long N, A[200005];
long long suf[200005];

int main()
{
	scanf("%lld", &N);
	for(int i = 1;i <= N;++i)
		scanf("%lld", &A[i]);
	suf[N + 1] = 0;
	for(int i = N;i >= 1;--i)
		suf[i] = (suf[i + 1] + A[i]) % mod;
	long long ans = 0;
	for(int i = 1;i < N;++i)
		ans = (ans + A[i] * suf[i + 1] % mod) % mod;
	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 6840
/**
 * auther: moririn_cocoa
 */
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define fi first
#define se second

int main(int argc, char* argv[]) {
  
  int a;
  int b;
  
  cin >> a;
  cin >> b;
  
  if ( a + b == 15 ) {
    
    cout << "+" << endl;
  }
  
  else if ( a * b == 15 ) {
    
    cout << "*" << endl;
  }
  
  else {
    
    cout << "x" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

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

	if (A[A.length() - 1] == B[0] && B[B.length() - 1] == C[0]) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	
}

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <deque>
using ll = long long;
int main()
{
    int N;
    ll C;
    std::cin >> N >> C;
    using P = std::pair<ll, ll>;
    std::deque<P> lines;
    auto add = [&](const P& l) {
        auto check = [](auto&& self, const P& l1, const P& l2, const P& l3) -> bool { return l1 < l3 ? self(self, l3, l2, l1) : (l3.second - l2.second) * (l2.first - l1.first) >= (l2.second - l1.second) * (l3.first - l2.first); };
        while (lines.size() >= 2 and check(check, *(lines.end() - 2), lines.back(), l)) { lines.pop_back(); }
        lines.push_back(l);
    };
    auto f = [&](const int i, const ll x) { return lines[i].first * x + lines[i].second; };
    auto get = [&](const ll x) {
        static int head = 0;
        for (; lines.size() - head >= 2 and f(head, x) > f(head + 1, x); head++) {}
        return f(head, x);
    };
    std::vector<ll> h(N);
    for (int i = 0; i < N; i++) { std::cin >> h[i]; }
    std::vector<ll> dp(N, 0);
    add({-2 * h[0], C + h[0] * h[0]});
    for (int i = 1; i < N; i++) {
        dp[i] = get(h[i]) + h[i] * h[i];
        add({-2 * h[i], C + h[i] * h[i] + dp[i]});
    }
    std::cout << dp[N - 1] << std::endl;
    return 0;
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int>vec(N, 0);
  for (int i=0; i < N; i++){
    cin >> vec.at(i);
  }
  int a = 1;
  int x = 0;
  while(x < N ){
    if (a == 2){
    cout << x << endl;
      break;
    }else{
     a = vec.at(a-1);
      x++;
    }
  }
  if (x > N-1){
    cout << "-1" << endl;
  }
}
 

Measured memory_bytes: 3764
#include <stdio.h>
 
int main(void)
{
    /*?????°??£?¨?*/
    int r,c,i,j,sum;
    int data[101][101];
     
    /*??\???*/
    scanf("%d %d",&r,&c);
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            scanf("%d",&data[i][j]);
        }
    }
     
    /*??????*/
    for(i=0;i<r;i++){
        sum=0;
        for(j=0;j<c;j++){
            sum+=data[i][j];
        }
        data[i][c]=sum;
    }
    for(i=0;i<=c;i++){
        sum=0;
        for(j=0;j<r;j++){
            sum+=data[j][i];
        }
        data[r][i]=sum;
    }
     
    /*??????*/
    for(i=0;i<=r;i++){
        for(j=0;j<=c;j++){
            if(j) printf(" ");
            printf("%d",data[i][j]);
        }
        printf("\n");
    }
    return 0;
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define print(obj) cout << obj << endl
#define scan(obj) cin >> obj

typedef long long ll;

using namespace std;

bool IsPrime(int num);

int main(void){
    ll n, p, temp = 2, ans = 1;
    vector<int> soinsu;
    cin >> n >> p;
    if(p == 1){
        print(1);
        return 0;
    }
    if(n == 1){
        print(p);
        return 0;
    }
    while(p >= temp * temp/*!IsPrime(p)*/){
        bool flag = true;
        if(p % temp == 0){
            soinsu.pb(temp);
            p /= temp;
            flag = false;
            continue;
        }
        temp++;
    }
    soinsu.pb(p);
    int tyouhuku = 1;
    rep(i, soinsu.size() - 1){
        if(soinsu[i] == soinsu[i + 1]){
            tyouhuku++;
        } else {
            tyouhuku = 1;
        }
        if(tyouhuku == n){
            ans *= soinsu[i];
            i++;
            tyouhuku = 1;
        }
    }
    print(ans);
}

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;


int H, W, A, B;
int a[1001][1001];
int main() {
    cin >> H >> W >> A >> B;

    REP(i, B) {
        REP(j, A) {
            a[i][j] = 1;
        }
    }

    for(int i=0; i<H-B; i++) {
        for(int j=0; j<W-A; j++) {
            a[H-i-1][W-1-j] = 1;
        }
    }

    REP(i, H) {
        REP(j, W) cout << a[i][j];
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 5120
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc;

	static final int INF=1<<28;
	static final double EPS=1e-9;

	void run(){
		sc=new Scanner(System.in);
		for(;;){
			int h=sc.nextInt();
			int m=sc.nextInt();
			int s=sc.nextInt();

			if(h==-1&&m==-1&&s==-1)
				break;

			h=2-h;
			m=0-m;
			s=0-s;

			if(s<0){
				s+=60;
				m--;
			}
			if(m<0){
				m+=60;
				h--;
			}

			println(String.format("%02d:%02d:%02d", h, m, s));

			h*=3;
			m*=3;
			s*=3;
			m+=s/60;
			s%=60;
			h+=m/60;
			m%=60;

			println(String.format("%02d:%02d:%02d", h, m, s));

		}
		sc.close();
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

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

Measured memory_bytes: 12000
n=int(input())
l=list(range(2,int(n**0.5//1+1)))
ans=n-1
count=0
for i in l:
    if n%i==0:
        a=i+int(n/i)-2
        ans=min(ans,a)
        count+=1
print(ans if count>0 else n-1)

Measured memory_bytes: 43252
#include <iostream>
#include <cstdio>
#include <cstring>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
template<class T> inline void read(T &x){
    x=0; 
    T f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch<='9' && ch>='0'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    x*=f;
}
int n,m;
int main(){
	read(n),read(m);
	dsu d(n);
	int x,y,z;
	for(int i=1;i<=m;i++){
		read(x),read(y),read(z);
		if(x==1){
			if(d.same(y,z)){
				printf("1\n");
			}
			else{
				printf("0\n");
			}
		}
		if(x==0){
			d.merge(y,z);
		}
	}
	return 0;
}


Measured memory_bytes: 3776
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney,chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun


#define PRI(s) cout << s << endl
#define PRIY PRI("Yes")
#define PRIN PRI("No")

int main() {
	int a, b;
	cin >> a >> b;
	if (a < 10 && b < 10)PRI(a * b);
	else PRI(-1);
	return 0;
}

Measured memory_bytes: 3672
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define Cpy(x,y) memcpy(x,y,sizeof(x))
#define Set(x,y) memset(x,y,sizeof(x))
#define FILE "4911"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const int N=5010;
const int M=4e6;
const int base=26;
const dd eps=1e-6;
const int inf=1e9;
const ll INF=1ll<<60;
const ll P=100000;
const int mod=1e9+7;
il ll read(){
  RG ll data=0,w=1;RG char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  if(ch=='-')w=-1,ch=getchar();
  while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
  return data*w;
}
il void file(){
  srand(time(NULL)+rand());
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
}

int n,k,fac[4000010],inv[4000010],f[4005][2005];
il void upd(int &a,int b){a+=b;if(a>=mod)a-=mod;}
il int C(int n,int m){
  //printf("%d,%d\n",n,m);
  return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
il int poww(int a,int b){
  RG int ret=1;
  for(;b;b>>=1,a=1ll*a*a%mod)
    if(b&1)ret=1ll*ret*a%mod;
  return ret;
}

int main()
{
  fac[0]=inv[0]=1;
  for(RG int i=1;i<=M;i++)fac[i]=1ll*fac[i-1]*i%mod;
  inv[M]=poww(fac[M],mod-2);
  for(RG int i=M-1;i;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;

  n=read();k=read();f[0][0]=1;if(k==1)return puts("1"),0;
  for(RG int i=1;i<=n;i++)
    for(RG int j=0;j<=i;j++){
      upd(f[i][j],f[i-1][j]);
      if(j)upd(f[i][j],1ll*f[i][j-1]*C(n*k-(j-1)*(k-1)-i-1,k-2)%mod*(n-j+1)%mod);
      //printf("f[%d][%d]=%d\n",i,j,f[i][j]);
    }
  printf("%d\n",f[n][n]);
  return 0;
}


Measured memory_bytes: 47616
#include <bits/stdc++.h>
using namespace std;
#define MAX 151200
typedef long long ll;
 
int main(void){
  ll N;
  while(cin >> N, N){
    int ans = 0;
    for(int cube = 0; cube * cube * cube <= MAX; cube++){
      for(int tr = 0; tr * (tr+1) * (tr+2) / 6 <= MAX; tr++){
    int cuben = cube * cube * cube;
    int trn = tr*(tr+1)*(tr+2)/6;
    if(cuben <= N){
      ans = max(ans, cuben);
    }
    if(trn <= N){
      ans = max(ans, trn);
    }
    if(cuben + trn <= N){
      ans = max(ans, cuben + trn);
    }
      }
    }
    cout << ans << endl;
  }
  return 0;
}

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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  int n;
  int64 a, b;
  cin >> n >> a >> b;
  vector<int64> xs(n);
  for (int i = 0; i < n; i++) {
    cin >> xs[i];
  }

  int64 l = 0;
  int64 u = 1E9;
  auto fn = [&](int64 k) -> bool {
    int64 c = 0;
    for(int64 x : xs) {
      if (x > b * k) {
        c += (x - b * k + (a - b - 1)) / (a - b);
      }
    }
    return c <= k;
  };
  while (u - l >= 2) {
    int64 m = (u + l) / 2;
    if (fn(m)) {
      u = m;
    } else {
      l = m;
    }
  }
  cout << u << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define inf  1e9+7
#define inf2 1e18
#define pb push_back
#define F first
#define S second
#define R return
#define C continue
#define B break
using namespace std;
ll q,h,l,d;
ll re;
ll ans;
int main()
{
    cin >> q >> h >> l  >> d;
    cin >> re ;
    ll nq=8*q;
    ll nh=4*h;ll nl=2*l;
    ans=(re/2)*(min(nq,min(nh,min(nl,d))));
    if(re%2)
    {
        ans+=min(4*q,min(2*h,l));
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
	long int i, j, index;
	long int r;
	long int sum;
	long int left, right;
	long int work, flg;
	long int ans;
	char str[500001];
	
	scanf("%ld", &r);
	
	printf("%ld", r * r);
	
	return 0;
}


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

int main() {
  int W,H,N;
  cin >> W >> H >> N;
  int Maxx=0,Minx=W,Maxy=0,Miny=H;
  int S = 0;
  for(int i=0; i < N; i++){
    int x,y,a;
    cin >> x >> y >> a;
    if(a==1){
      if(Maxx < x){
        Maxx=x;
      }
    }
    if(a==2){
      if(Minx > x){
        Minx=x;
      }
    }
    if(a==3){
      if(Maxy < y){
        Maxy=y;
      }
    }
    if(a==4){
      if(Miny > y){
        Miny=y;
      }
    }
  }
  
  S=(Minx-Maxx)*(Miny-Maxy);
  if(Maxx > Minx || Maxy > Miny){
    S=0;
  }
  cout << S << endl;
}

Measured memory_bytes: 256
// by adiforluls
#pragma GCC optimize ("-O2")
#include<bits/stdc++.h>
#define FAST        ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define mii         map<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define clz(a)      __builtin_clz(a) // count leading zeroes
#define ctz(a)      __builtin_ctz(a) // count trailing zeroes
#define popc(a)     __builtin_popcount(a) // count set bits (for ints only diff for ll)
#define lul         1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define SIZE        1000005
#define F           first
#define S           second
#define debug(x)        cerr << #x << " = " << x << endl;
#define mod         998244353
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " = " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " = " << arg1<<" |";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
#define endl        '\n'
const int INF = 0x3f3f3f3f;

vector<pii> adj[100005];
int vis[100005]={0},n;
int col[100005]={0};
void dfs(int node)
{
  vis[node]=1;
  for(auto i:adj[node])
  {
    if(!vis[i.F])
    {
      if(i.S&1) col[i.F]=!col[node];
      else col[i.F]=col[node];
      dfs(i.F);
    }
  }
}
int main()
{
    FAST;
    //  #ifndef ONLINE_JUDGE
//      freopen("input.txt", "r", stdin);
//      freopen("output.txt", "w", stdout);
//  #endif
    int t; t=1;
    while(t--)
    {
       int n; cin>>n;
       rep(i,1,n)
       {
         int x,y,wt; cin>>x>>y>>wt;
         adj[x].pb({y,wt});
         adj[y].pb({x,wt});
       }
       dfs(1);
       rep(i,1,n+1) cout<<col[i]<<endl;
    }
}

Measured memory_bytes: 7936
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
#define INF 2000'000'000

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	//freopen("in", "r", stdin);
	int x;
	cin >> x;
	int ans = 8;
	for(int max = 599; x > max; ans--, max += 200);
	cout << ans << endl;
	return 0;
}


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

std::string a,b,c;


int main() {

    std::cin>>a>>b>>c;

    if(a.back()==b.front()&&b.back()==c.front())
        std::cout<<"YES"<<std::endl;
    else
        std::cout<<"NO"<<std::endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int X,Y;
  cin>>X>>Y;
  if(Y%2==1)
  {
    cout<<"No"<<endl;
  }else
  {
    if(X*4<Y)
    {
      cout<<"No"<<endl;
    }else if(X*2>Y)
    {
      cout<<"No"<<endl;
    }else
    {
      cout<<"Yes"<<endl;
    }
  }
}

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

using namespace std;

/**
 * AOJの過去問を参考にしました。
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B&lang=jp
 *
 * うしさんのコード(AOJのコード)をパクッてしまった。
 */

struct UnionFind
{
	vector< int > data;

	UnionFind(int sz)
	{
		data.assign(sz, -1);
	}

	bool unite(int x, int y)
	{
		x = find(x), y = find(y);
		if (x == y) return (false);
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return (true);
	}

	int find(int k)
	{
		if (data[k] < 0) return (k);
		return (data[k] = find(data[k]));
	}

	int size(int k)
	{
		return (-data[find(k)]);
	}
};

struct LowLink
{
	UnionFind uf;
	vector< vector< int > > g;
	vector< int > used, ord, low, parent;

	LowLink(size_t v) : g(v), used(v, 0), ord(v), low(v), uf(v), parent(v, -1) {}

	virtual void add_edge(int x, int y)
	{
		g[x].push_back(y);
		g[y].push_back(x);
	}

	void dfs(int idx, int &k, int par = -1)
	{
		used[idx] = true;
		ord[idx] = k++;
		low[idx] = ord[idx];

		for (auto &to : g[idx]) {
			if (!used[to]) {
				dfs(to, k, idx);
				low[idx] = min(low[idx], low[to]);
				parent[to] = idx;
				if (ord[idx] >= low[to]) uf.unite(idx, to);
			}
			else if (to != par) {
				low[idx] = min(low[idx], ord[to]);
			}
		}
	}

	void dfs()
	{
		int k = 0;
		dfs(0, k);
	}
};

struct ArticulationPoints : LowLink
{
	ArticulationPoints(size_t v) : LowLink(v) {}

	vector< int > build()
	{
		LowLink::dfs();
		vector< int > vs;
		int sum = 0;
		for (int i = g.size() - 1; i >= 1; i--) {
			if (parent[i] == 0) ++sum;
			else if (ord[parent[i]] <= low[i]) vs.push_back(parent[i]);
		}
		if (sum > 1)vs.push_back(0);
		sort(begin(vs), end(vs));
		vs.erase(unique(begin(vs), end(vs)), end(vs));
		return (vs);
	}
};

struct BiConnectedComponents : LowLink
{
	vector< pair< int, int > > edges;
	vector< int > comp;

	BiConnectedComponents(size_t v) : LowLink(v), comp(v) {}

	void add_edge(int x, int y)
	{
		LowLink::add_edge(x, y);
		edges.push_back(minmax(x, y));
	}

	int operator[](int k)
	{
		return (comp[k]);
	}

	vector< pair< int, int > > build(vector< vector< int > > &t)
	{
		LowLink::dfs();
		int ptr = 0;
		vector< int > cc(g.size());
		for (int i = 0; i < g.size(); i++) {
			if (i == uf.find(i)) cc[i] = ptr++;
		}

		t.resize(ptr);
		for (int i = 0; i < g.size(); i++) {
			comp[i] = cc[uf.find(i)];
		}
		vector< pair< int, int > > vs;
		for (auto &e : edges) {
			int x = comp[e.first], y = comp[e.second];
			if (x == y) continue;
			vs.emplace_back(e.first, e.second);
			t[x].push_back(y);
			t[y].push_back(x);
		}
		sort(begin(vs), end(vs));
		return (vs);
	}
};

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

	int n, m;
	cin >> n >> m;
	BiConnectedComponents graph(n);

	// うしさん許して
	vector< vector< int > > ei1333;
	for (int i = 0; i < m; i++) {
		int s, t;
		cin >> s >> t;
		s--; t--;
		graph.add_edge(s, t);
	}

	int res = 0;
	for (auto &p : graph.build(ei1333)) {
		res++;
	}

	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int i, j;
    int h, w;
    
    while(scanf("%d %d", &h, &w), h > 0 && w > 0){
        for(i = 0; i < h; ++i){
            for(j = 0; j < w; ++j){
                putchar(i == 0 || j == 0 || i == h - 1 || j == w - 1 ? '#' : '.');
            }
            
            putchar('\n');
        }
        
        putchar('\n');
    }
    
    return 0;
}


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

int main() {
    int x,n;
    cin >> x >> n;
    vector<int> p(n);
    vector<int> num(301,0);
    for(int i=0; i<n; i++){
        cin >> p[i];
        num[p[i]+100]++;
    }
    for(int i=0; i<=100; i++){
        if(num[x+100-i]==0){
            cout << x - i << endl;
            break;
        }else if(num[x+100+i]==0){
            cout << x + i << endl;
            break;
        }
    }
}

Measured memory_bytes: 3632
X, Y = map(int, input().split())

prize = [300000, 200000, 100000]

ans = 0

if 1 <= X <= 3:
    ans += prize[X-1]
if 1 <= Y <= 3:
    ans += prize[Y-1]

if X == 1 and Y == 1:
    ans += 400000

print(ans)


Measured memory_bytes: 2940
n = gets.to_i

positions = []

sample = []
n.times do
    x, y, h = gets.split.map(&:to_i)
    sample = [x, y, h] if h > 0
    positions << [x, y, h]
end


res_x = res_y = res_h = 0

0.upto(100) do |cx|
    valid = true
    0.upto(100) do |cy|
        valid = true

        positions.each do |pos|
            ch = [0, sample[2] + (cx - sample[0]).abs + (cy - sample[1]).abs].max
            res_x = cx
            res_y = cy
            res_h = ch

            if pos[2] != [0, ch - (cx - pos[0]).abs - (cy - pos[1]).abs].max
                valid = false
            end

        end

        break if valid
    end
    break if valid
end

puts [res_x, res_y, res_h].join(' ')

Measured memory_bytes: 1788
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int vis[3005][3005];
long long dp[3005][3005];
int a[3005];
long long min_(long long x,long long y) {return x>y?y:x;}
long long max_(long long x,long long y) {return x>y?x:y;}
long long dfs(int l,int r) {
	if(l>r) return 0;
	if(vis[l][r]) return dp[l][r];
	vis[l][r]=true;
	int d=n-(r-l+1);
	if(d & 1) {
		dp[l][r]=min_(dfs(l+1,r)-a[l],dfs(l,r-1)-a[r]);           //Jino删数 
	}
	else {
		dp[l][r]=max_(dfs(l+1,r)+a[l],dfs(l,r-1)+a[r]);
	}
	return dp[l][r];
}
int main () {
	cin>>n;
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
    cout<<dfs(1,n);
    
}

Measured memory_bytes: 105344
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
    string S;
    cin>>S;
    int a=(int)'a';
    bool isa=false;
    rep2(i,a,a+26){
        isa=false;
        rep(j,S.size()){
            if(S.at(j)==(char)i){
                isa=true;
            }
        }
        if(isa){
            continue;
        }else{
            cout << (char)i << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main{
	public static void main(String args[]) {
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		int m = scn.nextInt();
		int[] DP = new int[n + 1];
		for (int i = 1; i < n + 1; i++) {
			DP[i] = Integer.MAX_VALUE;
		}

		for (int j = 0; j < m; j++) {
			int val = scn.nextInt();
			for (int i = 1; i < n + 1; i++) {
				if (i >= val) {
					DP[i] = Math.min(DP[i], DP[i - val] + 1);
				}
			}
		}
		System.out.println(DP[n]);
		scn.close();
	}
}



Measured memory_bytes: 26928
n=int(input())

A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

s=B[0]
for i in range(1,n):
  s+=B[i]
  if A[i-1]==A[i]-1:
    s+=C[A[i-1]-1]

print(s)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

namespace {
	int cnt, m;
	vector<int> G;

	void InsertionSort(vector<int>& A, int n, int g)
	{
		for (int i = g; i < n; ++i)
		{
			int v = A[i];
			int j = i - g;

			while (j >= 0 && A[j] > v) {
				A[j + g] = A[j];
				j -= g;
				cnt++;
			}

			A[j + g] = v;
		}
	}

	void ShellSort(vector<int>& A, int n)
	{
		cnt = 0;
		G.push_back(1);
		for (int i = 1; i <= n; ++i)
		{
			int g = pow(4, i) + 3 * pow(2, i - 1) + 1;
			if (g <= n) G.push_back(g);
			else { m = i; reverse(G.begin(), G.end()); break; }
		}

		for (int i = 0; i < m; ++i)
			InsertionSort(A, n, G[i]);
	}
}

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

	vector<int> A(n, 0);
	for (int i = 0; i < n; ++i)
		cin >> A[i];

	ShellSort(A, n);

	cout << m << endl;
	for (int i = 0; i < m; ++i) {
		cout << G[i];
		i != m - 1 ? cout << " " : cout << endl;
	}
	cout << cnt << endl;
	for (int i = 0; i < n; ++i)
		cout << A[i] << endl;

	return 0;
}

Measured memory_bytes: 4964
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc1 = new Scanner(System.in);

		int[] input = new int[5];

		input[0] = sc1.nextInt();
		input[1] = sc1.nextInt();
		input[2] = sc1.nextInt();
		input[3] = sc1.nextInt();
		input[4] = sc1.nextInt();

		int[] test = new int[5];

		for (int i=0; i < 5 ; i++) {
			test[i] = input[i]%10;
		}

		int idx = 0;
		for (int i=0; i < 4 ; i++) {
			if (test[i+1] != 0 && test[idx] > test[i+1]) {
				idx = i+1;
			}
		}

		int ans = 0;

		for (int i=0; i < 5 ; i++) {
			if (i == idx) {
				continue;
			}
			else {
				ans += input[i];
				if (input[i]%10 != 0) {
					ans += 10-(input[i]%10);
				}
				//System.out.println(ans);
			}
		}

		ans += input[idx];
		System.out.println(ans);

		sc1.close();

	}

}

Measured memory_bytes: 23764
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

struct Pt{
	int x,y;
	Pt(){}
	Pt(int x,int y):x(x),y(y){}
};

int checked[110][110];

int main() {
	int n;
	Pt mp[110][110];
	for(;n=in();){
		int x,y;
		for(y=0;y<110;y++){
			for(x=0;x<110;x++){
				mp[y][x].x=0;
				mp[y][x].y=0;
			}
		}for(y=0;y<n;y++){
			for(x=0;x<n;x++){
				mp[y][x].x=in();
				mp[y][x].y=in();
			}
		}
		Pt pt;
		memset(checked,0,sizeof(checked));
		int res=0;
		for(y=0;y<n;y++){
			for(x=0;x<n;x++){
				if(checked[y][x])continue;
				int i;
				pt=mp[y][x];
				for(i=0;i<10010;i++){
					pt=mp[pt.y][pt.x];
					if(pt.x==x&&pt.y==y)break;
				}
				//cout<<pt.x<<" "<<pt.y<<" "<<x<<" "<<y<<endl;
				if(i<10010){
					res++;
					for(i=0;i<10010;i++){
						checked[pt.y][pt.x]=1;
						pt=mp[pt.y][pt.x];
						if(pt.x==x&&pt.y==y)break;
					}
				}else checked[y][x]=1;
				//int xx,yy;
				/*for(yy=0;yy<n;yy++){
					for(xx=0;xx<n;xx++){
						cout<<checked[yy][xx];
					}
					cout<<endl;
				}
				cout<<endl;*/
			}
		}
		cout<<res<<endl;
	}
}

Measured memory_bytes: 1028
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
int old,k;
int main(){
	cin>>old>>k;
	if(old<6){
		cout<<0;
	}
	else if(old<13){
		cout<<k/2;	
	}
	else{
		cout<<k;
	}
}

Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {
    static int n;
    static Circle circle[] = new Circle[24];
    static int[] state = new int[20000000];
    static int[] two = new int[25];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        powTwo();

        while (true){
            n = sc.nextInt();
            if (n==0) break;

            for (int i = 0; i < 20000000; i++) {
                state[i] = 0;
            }
            for (int i = 0; i < n; i++) {
                circle[i] = new Circle(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
                overCircle(i);
            }

            System.out.println(remove(0, 0));
        }
    }

    static void powTwo() {
        two[0] = 1;
        for (int i = 1; i < 25; i++) {
            two[i] = two[i-1]*2;
        }
    }

    static void overCircle(int i) {
        for (int j = 0; j < i; j++) {
            int l = (int)(Math.pow(circle[j].x-circle[i].x,2)+Math.pow(circle[j].y-circle[i].y,2));
            if (Math.pow(circle[j].r+circle[i].r,2)>l){
                circle[i].over[j] = 1;
                circle[i].cnt++;
            }
        }
    }

    static int remove(int cnt, int s) {
        state[s] = 1;
        int ans = cnt;

        for (int i = 0; i < n; i++) {
            if (circle[i].flag==1 || circle[i].cnt>0) continue;

            for (int j = i+1; j < n; j++) {
                if (circle[j].flag==0&&circle[j].cnt==0&&circle[i].c==circle[j].c){
                    if (state[s+two[i]+two[j]]==1) continue;
                    circle[i].flag = circle[j].flag = 1;
                    for (int k = 0; k < n; k++) {
                        if (circle[k].over[i]==1) circle[k].cnt--;
                        if (circle[k].over[j]==1) circle[k].cnt--;
                    }
                    ans = Math.max(remove(cnt+2, s+two[i]+two[j]), ans);
                    circle[i].flag = circle[j].flag = 0;
                    for (int k = 0; k < n; k++) {
                        if (circle[k].over[i]==1) circle[k].cnt++;
                        if (circle[k].over[j]==1) circle[k].cnt++;
                    }
                }
            }
        }
        return ans;
    }

    static class Circle{
        int x, y, r, c;
        int[] over = new int[24];
        int cnt = 0, flag = 0;
        Circle(int s, int t, int u, int v){
            x = s; y = t; r = u; c = v;
        }
    }
}

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

using namespace std;
int main(){
	string s;
  	cin >> s;
	long long ans=0;
  	vector<long long> vec;
  
  	vec.push_back(1);
  	for(int i=1; i<s.size();i++){
      	if(s[i]==s[i-1]){
          	vec.back()++;
        }else{
          	vec.push_back(1);
        }
    }
  	bool frag = (s.front()=='<');
      for(int i=1;i<vec.size();i++){
      	if(frag&&(vec[i]>vec[i-1])){
          	vec[i-1]--;
        }else{
          	vec[i]-=(frag==true);
        }
        ans+=vec[i-1]*(vec[i-1]+1)/2;
      	frag=!frag;
      }
  	ans+=vec.back()*(vec.back()+1)/2;
  	cout << ans;
}
  	
  	

Measured memory_bytes: 3068
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdlib>
#include <iterator>
using namespace std;
const int N=  1e5 + 7;
int a[N];
//#define TEST
int main()
{
#ifdef TEST
	freopen("data.in", "r", stdin);
	freopen("data.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	int n;
	while(cin >> n) {
		for (int i= 1; i<= n; ++i) {
			cin >> a[i];
		}
		int cnt = 0;
		for(int i = 1; i <= n; ++i) {
			if(a[i] != i) continue;
			cnt++;
			++i;
		}
		cout << cnt << endl;
	}

	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(h, n, t)
{
    scanf("%d%d", &h, &n);
    while(n-- && h>=0)
    {
        scanf("%d", &t);
        h-=t;
    }

    printf("%s\n", (h<=0)?"Yes":"No");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int N, A, B, C;
vec<string> s;
vec<char> ans;

void dfs(int now, int a, int b, int c) {
    if (ans.size() == N) {
        cout << "Yes" << endl;
        for (auto e : ans)
            cout << e << endl;
        exit(0);
    }
    if (s[now] == "AB") {
        if (a != 0) {
            ans.push_back('B');
            dfs(now + 1, a-1, b+1, c);
            ans.pop_back();
        }
        if(b!=0){
            ans.push_back('A');
            dfs(now + 1, a+1, b-1, c);
            ans.pop_back();
        }
    }
    if (s[now] == "AC") {
        if (a != 0) {
            ans.push_back('C');
            dfs(now + 1, a-1, b, c+1);
            ans.pop_back();
        }
        if(c!=0){
            ans.push_back('A');
            dfs(now + 1, a+1, b, c-1);
            ans.pop_back();
        }
    }
     if (s[now] == "BC") {
        if (b != 0) {
            ans.push_back('C');
            dfs(now + 1, a, b-1, c+1);
            ans.pop_back();
        }
        if(c!=0){
            ans.push_back('B');
            dfs(now + 1, a, b+1, c-1);
            ans.pop_back();
        }
    }
}

int main() {
    cin >> N >> A >> B >> C;
    s.resize(N);
    rep(i, N) cin >> s[i];
    dfs(0, A, B, C);
    cout << "No" << endl;
}

Measured memory_bytes: 14396
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define FORR(x, arr) for(auto& x:arr)
#define ITR(x, c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;
typedef pair<int, int> P;

ll a[5];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	FOR(i, 3) cin >> a[i];
	ll mi = 1LL<<60;
	FOR(i, 3) {
		ll x = 1;
		FOR(j, 3) {
			if (i != j) x *= a[j];
		}
		if (a[i] & 1) mi = min(mi, x);
		else mi = 0;
	}
	cout << mi << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int Num,Leg;
  cin >> Num >> Leg;
  bool flag = false;
  for(int i=0; i<=Num; i++){
    if(2*i + 4*(Num-i) == Leg) flag = true;
  }
  if(flag){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

#define CH(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)

using namespace std;

int N,M,K,D[20],v[105][105];
bool visit[(1<<16)];
int bits[105] = {};

int main() {
  cin>>N>>M>>K;
  REP(i,0,M){
    int d;
    cin>>d;
    D[i] = d-1;
    bits[D[i]] = (1<<i);
  }
  REP(i,0,N){
    REP(j,0,K){
      cin>>v[i][j];
    }
  }
  REP(i,0,(1<<16)) visit[i] = false;
  queue< pair<int, int> > stq;  //????????¨?±?????????¨??¶???, ????????????
  stq.push(make_pair((1<<M)-1, 0));
  visit[(1<<M)-1] = true;;
  while(!stq.empty()){
    int state = stq.front().first;
    int step = stq.front().second;
    stq.pop();

    REP(j,0,K){ /*??¶???state????????????K????????????????????¨?????????????????????*/
      int nextState = 0;
      /*
      int nextState = state;
      vector<int> fromv;
      vector<int> tov;
      */
      REP(i,0,M){
        if(state & (1<<(i/*D[i]*/))){
          //fromv.push_back(/*i*//*D[i]*/bits[D[i]]);
          ////REP(k,0,M) if(v[D[i]][j]-1 == D[k]) tov.push_back(k);
          //if(bits[v[D[i]][j]-1] != 0) tov.push_back(bits[v[D[i]][j]-1]);
          if(bits[v[D[i]][j]-1] != 0) nextState |= bits[v[D[i]][j]-1];
        }
      }
      /*
      //REP(i,0,fromv.size()) nextState &= ~(1<<fromv[i]); //from????????????????????????????????¨???
      REP(i,0,fromv.size()) nextState &= ~fromv[i];
      //REP(i,0,tov.size()) nextState |= (1<<tov[i]);  //to????????????????????????????????????
      REP(i,0,tov.size()) nextState |= tov[i];
      */
      if(nextState==0){
        cout<<step+1<<endl;
        return 0;
      }
      if(!visit[nextState]){
        stq.push(make_pair(nextState, step+1));
        visit[nextState] = true;
      }
    }
  }

  return 0;
}

Measured memory_bytes: 3396
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  int n, k;
  cin >> n >> k;
  V a(n);
  REP(i, n) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int i = 0, cnt = 0;
  V x;
  while (i < n) {
    cnt = 1;
    while (i < n-1 && a[i] == a[i+1]) {
      i++;
      cnt++;
    }
    x.push_back(cnt);
    i++;
  }
  sort(x.begin(), x.end());
  int sum = 0;
  REP(i, (int)x.size()-k) {
    sum += x[i];
  }
  dump(sum);
  return 0;
}


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

int main()
{
    string S, atoz;
    int sum = 0;
    cin >> S;
    atoz = "abcdefghijklmnopqrstuvwxyz";
    vector<bool> A(27);

    for (int i = 0; i < S.size(); i++)
    {
        for (int j = 0; j < atoz.size(); j++)
        {
            if (S.at(i) == atoz.at(j) && A.at(j) == false)
            {
                A.at(j) = true;
                sum++;
            }
        }
    }

    for (int i = 0;;i++)
    {
        if(A.at(i)==false)
        {
            cout << atoz.at(i) << endl;
            break;
        }else if(sum>=26)
        {
            cout << "None" << endl;
            break;
        }
    }
}


Measured memory_bytes: 512
n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
mod=pow(10,9)+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1<<n):
    cnt=0
    #　bitが何個たつか調べる
    for j in range(n):
        if (i>>j)&1:
            cnt+=1
    for j in range(n):
        if (i >> j) & 1:
            dp[i] += dp[i ^ (1 << j)] * a[j][cnt-1]
            dp[i]%=mod

print(dp[-1])

Measured memory_bytes: 59484
n, m, x, y = map(int, input().split())
x_list = [int(data) for data in input().split()]
y_list = [int(data) for data in input().split()]

if x < y and max(x_list) < min(y_list) and max(x_list) > x and min(y_list) < y:
    print("No War")
else:
    print("War")


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

int main(){
  int A,B;
  cin >> A >> B;
  if(A * B == 2){
    cout << 3 << endl;
  }else if(A * B == 3){
    cout << 2 << endl;
  }else{
    cout << 1 << endl;
  }
}


Measured memory_bytes: 256