akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=3000,mod=1000000007;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

char s[N+9];
int n,nxt[N+9];

void into(){
  int m;
  scanf("%d%d",&n,&m);
  scanf("%s",s+1);
  for (int i=1;i<=m;++i){
	int l,r;
	scanf("%d%d",&l,&r);
	nxt[l]=max(nxt[l],r);
  }
}

int a[N+9];

void Get_a(){
  for (int i=1;i<=n;++i) a[i]=s[i]-'0'+a[i-1];
  a[n+1]=a[n];
}

void Get_nxt(){
  for (int i=1;i<=n+1;++i){
	if (!nxt[i]) nxt[i]=i;
	nxt[i]=max(nxt[i],nxt[i-1]);
  }
}

int dp[N+9][N+9];

void Get_dp(){
  dp[1][a[nxt[1]]]=1;
  for (int i=1;i<=n;++i)
	for (int j=0;j<=n;++j){
	  if (!dp[i][j]) continue;
	  int l=nxt[i],r=nxt[i+1],c0=nxt[i]-i+1-j,c1=j;
	  if (c1) sadd(dp[i+1][j+a[r]-a[l]-1],dp[i][j]);
	  if (c0) sadd(dp[i+1][j+a[r]-a[l]],dp[i][j]);
	}
}

void work(){
  Get_a();
  Get_nxt();
  Get_dp();
}

void outo(){
  printf("%d\n",dp[n+1][0]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 33920
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int A = cin.nextInt();
        int B = cin.nextInt();

        int s = 0;
        for (int i = 1; i <= N; i++) {
            int x = sum(i);
            if (x >= A && x <= B) {
                s += i;
            }
        }

        System.out.println(s);
    }

    static int sum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}

Measured memory_bytes: 21844
N=int(input())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
U=list(map(int,input().split()))

goukei=0

before=1000
for i in range(N):
    goukei+=T[S[i]-1]
    if before+1==S[i]:
        goukei+=U[S[i]-2]
    
    before=S[i]
    
print(goukei)

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

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

    int X = 1;
    for (int i = 0; i < M; i++)
    {
        X *= 2;
    }
    X *= M * 1900 + (N - M) * 100;
    cout << X << endl;
}


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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
bool dp[100005];
int n,k,a[101];
void solve(){
    cin>>n>>k;
    rep(i,1,n+1) cin>>a[i];
    dp[0]=0;
    rep(i,1,k+1){
        rep(j,1,n+1){
            if(i<a[j]) continue;
            dp[i]|=!dp[i-a[j]];
        }
    }
    if(dp[k]) cout<<"First"<<endl;
    else cout<<"Second"<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;

int N;
int G[101][101];
bool used[101];

int prim()
{
   int sum = 0;
   priority_queue< pii, vector<pii>, greater<pii> > pq;
   pq.push( pii(0, 0) );

   while( !pq.empty() ){
      const pii tmp = pq.top(); pq.pop();
      if( tmp.fi == -1 || used[ tmp.se ]++ )continue;
      sum += tmp.fi;

      rep(i, N)
         pq.push( pii( G[tmp.se][i], i ) );
   }
   return (sum);
}

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

   rep(i, N)rep(j, N){
      cin >> G[i][j];
   }
   cout << prim() << '\n';
}



Measured memory_bytes: 3264
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
  int a[10];

  while(cin>>a[0]){
    for(int i = 1; i < 10; ++i) cin >> a[i];
    sort(a, a+10);
    for(int i = 0; i < 3; ++i)
      cout << a[9-i] << endl;
  }

  return 0;
}

Measured memory_bytes: 1176
#include<stdio.h>

int main() {

    int n;
    int a[20], b[20], c[20];
    int satisfy;
    int before;
    scanf("%d", &n);

    int count = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    for (int i = 0; i < n - 1; i++) {
        scanf("%d", &c[i]);
    }

    satisfy = 0;
    before = 100;
    for (int i = 0; i < n; i++) {
        satisfy = satisfy + b[a[i] - 1];
        if (before + 1 == a[i]) {
            satisfy = satisfy + c[before - 1];
        }
        before = a[i];
    }
    printf("%d", satisfy);
    return 0;
}



Measured memory_bytes: 128
import time
import copy

start_time = time.time()

#input
D = int(input())
c_list = list(map(int, input().split()))

s_grid = []
for i in range(D):
    array = list(map(int, input().strip().split(' ')))
    s_grid.append(array)

def calculate_score(d,t,last):
    score = s_grid[d][t]
    last[t] = -1
    for i in range(26):
        score -= c_list[i]*(last[i]+1)
    return score

t_list = [] #task_list
last_list = [0] * 26

for k in range(0,D):
    X = -1  # k-日目に変える番号を探す
    p = 0
    for i in range(26):  # 26通り試す
        tmp = calculate_score(k,i,last_list)
        if tmp > p:
            X = i
            p = tmp

    #最大のXを投入
    t_list.append(X)
    last_list = [n+1 for n in last_list]
    last_list[X] = 0

    if time.time() - start_time > 1.9:
        break

for j in range(len(t_list)):
    print(int(t_list[j]) + 1)

Measured memory_bytes: 9484
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <bitset>
#include <unordered_map>

using ll = long long;

using namespace std;

using bs = bitset<26>;
#define INF 200010

#include <map>
#include <set>
// vecのなかの全要素について座標圧縮を行い、元座標->圧縮後座標というmapを作る
// O(NlogN) 座圧後のサイズを返す
// org: もともとの各iに対する座標 値渡しなので破壊しません
// zip: 圧縮
// unzip: 復元
template <typename T>
int compress(vector<T> org, map<T, int> &zip, vector<T> &unzip) {
    sort(org.begin(), org.end()); 
    org.erase(unique(org.begin(), org.end()), org.end()); // vecの各要素を小さい順に重複を無くして並べたもの
    int i = 0;
    for (auto &oi : org) {
        zip[oi] = i;
        unzip.push_back(oi);
        i++;
    }
    return i;
}

int main() {
    string s;
    cin >> s;
    int len = s.size();
    vector<bs> rui(1, 0);
    for (int i=0; i<len; i++) {
        rui.push_back(rui.back());
        rui.back().flip(s[i] - 'a');
    }
    unordered_map<bs, int> dp;
    dp[0] = 0;
    for (int i=0; i<=len; i++) {
        for (int j=0; j<=26; j++) {
            bs from = rui[i];
            if (j > 0) from = from.flip(j-1);
            if (!dp.count(rui[i])) dp[rui[i]] = INF;
            if (!dp.count(from)) dp[from] = INF;
            dp[rui[i]] = min(dp[rui[i]], dp[from] + 1);
        }
    }
    cout << max(dp[rui[len]], 1) << '\n';
    return 0;
}

Measured memory_bytes: 171908
#include <bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
typedef long long ll;
using namespace std;
long long a,b,c,k;
int main(){
	cin>>a>>b>>c>>k;
	if (k%2==0){
		cout<<a-b;
	}else{
		cout<<b-a;
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;

const int N=100010;
int n,A,B,p[N],cnt1,cnt2,cnt3;

int main(){
	scanf("%d%d%d",&n,&A,&B);
	rep(i,1,n){
		scanf("%d",&p[i]);
		if (p[i]<=A) cnt1++;
		if (p[i]>A && p[i]<=B) cnt2++;
		if (p[i]>B) cnt3++;
	}
	printf("%d\n",min(cnt1,min(cnt2,cnt3)));
	return 0;
}

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

int main() {
  unsigned N;
  std::cin >> N;
  std::vector<unsigned long long> a(3ul * N);
  for (unsigned i = 0; i < 3u * N; ++i) {
    std::cin >> a[i];
  }
  std::sort(a.begin(), a.end());
  unsigned index = 3u * N - 1u;
  unsigned long long ans = 0ull;
  for (unsigned i = 0; i < N; ++i) {
    --index;
    ans += a[index];
    --index;
  }
  std::cout << ans;
  return 0;
}


Measured memory_bytes: 2560
while True:
    try:
        b = input()
    except:
        break
    if 'the' in b or 'this' in b or 'that' in b:
        print(b)
    for i in range(1,26):
        c = ''
        for j in b:
            if(j == 'z'):
                c += ('a')
            elif(str.isalpha(j) == 1):
                c += (chr(ord(j) + 1))
            else:
                c += j
        if 'the' in c or 'this' in c or 'that' in c:
            print(c)
            break
        b = c

Measured memory_bytes: 7288
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/



int main() {
	string S, T;
	cin >> S >> T;
	string C = S + S;
	int Z = S.size();
	int cnt = 0;
	rep(i, Z) {
		rep(j, Z) {
			if (T[j] == C[i + j]) {
				cnt++;
			}
		}
		if (cnt == Z) {
			cout << "Yes" << endl;
			return 0;
		}
		cnt = 0;
	}
	cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
	int N,i,j;
	cin>>N;
	vector<int> A(N);
	for (i=0;i<N;i++){
		cin>>A[i];
	}
	int Max=0;
	for (i=0;i<N-1;i++){
		for (j=i+1;j<N;j++){
			int d=A[i]-A[j];
			if (d<0){
				d=-d;
			}
			if (Max<d){
				Max=d;
			}
		}
	}
	cout<<Max<<endl;
	return 0;
}

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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second

#ifdef OJ
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#else
#define debug(x)
#define debugv(x)
#endif

#define all(x) (x).begin(), (x).end()
#define rsort(x) sort((x).rbegin(), (x).rend())
#define sz(x) ((int)x.size())
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n, e) for (int i = (int)(n); i >= (int)(e); --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
#define RETURN(x) do{cout << (x) << '\n'; return 0;}while(0)
#define RETURNV(x) do{cout << (x) << '\n'; return ;}while(0)

const int MOD = 1e9+7;
const int MAXN = 2e6+3;
const int INF = 1e9;

void solve() {
    int n,m,k; cin >> n >> m >> k;
    vector<int> a(n+1), b(m+1);
    fore(i,1,n) cin >> a[i];
    fore(i,1,m) cin >> b[i];
    
    int i = 0, j = 0;
    LL sum = 0;
    while(i < n) {
        if(sum + a[i+1] <= k) sum += a[++i];
        else break;
    }
    while(j < m) {
        if(sum + b[j+1] <= k) sum += b[++j];
        else break;
    }
    int ans = i+j;
    while(i) {
        sum -= a[i--];
        while(j < m && sum + b[j+1] <= k) sum += b[++j];
        mmax(ans, i+j);
    }
    cout << ans << '\n';
}

int main(int argc, char **argv) {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    int ntest = 1;
    int tt = 1;
    while(ntest--) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 4740
from collections import deque

n,q = map(int,input().split())
r = [[] for _ in range(n)]
bonus = [0] * n
score = [0] * n

for i in range(n-1):
    a,b = map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
for i in range(q):
    p,x = map(int,input().split())
    bonus[p-1] += x
q = deque()
q.append(0)
used = [False]*n
used[0] = True
score[0] = bonus[0]

while q:
    p = q.popleft()
    for i in r[p]:
        if not used[i]:
            used[i] = True
            score[i] += score[p] + bonus[i]
            q.append(i)
        
print(*score)

Measured memory_bytes: 107076
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<array>
#include<vector>
#include<functional>
#include<unordered_map>
#include<map>
#include<numeric>
#include<limits>
#include<utility>
#include<queue>
#include<random>
#include<math.h>
using namespace std;

int main() {
	int count = 0;
	string str;
	cin >> str;
	for (int i = 0; i < 3; i++)
	{
		if (str[i] == '1')
		{
			count++;
		}

	}

	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve

int main(int argc, char const* argv[])
{
  string tmp;
  string s[8];
  unordered_map<int, string> mp;
  mp[18] = "A";
  mp[48] = "B";
  mp[6] = "C";
  mp[30] = "D";
  mp[20] = "E";
  mp[34] = "F";
  mp[16] = "G";
  do{
    rep(i, 8){
      if(!getline(cin, s[i])){
        return 0;
      }
    }
    int at = -1;
    int sum = 0;
    rep(i, 8){
      rep(j, 8){
        if(s[i][j] == '1'){
          if(at == -1){
            at = i * 8 + j;
          }else{
            sum += i * 8 + j - at;
          }
        }
      }
    }
    cout << mp[sum] << endl;
  }while(getline(cin, tmp));
	return 0;
}



Measured memory_bytes: 2988
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n;
  string s;
  cin >> n >> s;
  char c = 'A';
  int ans = 0;
  REP(i, n) {
    if (c != s[i]) {
      ans++;
      c = s[i];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int ans=0;
		int now=0;

		for(int i=1;i<=n;i+=2) {
			for(int j=1; j<=i;j++) {
				if(i%j==0) {
					now++;
				}
			}
			if(now==8) {
				ans++;
			}
			now=0;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 21844
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

int n, m;

std::set<std::pair<int, int> > edges0;
std::vector<int> edges[700];
int colors[700];
std::vector<int> cliques;
std::vector<int> states;
std::vector<int> t;
std::vector<int> u;

bool bipartite;

int color(int x, int p){
  int r = 0;
  for(auto y: edges[x]){
    if(y == p) continue;
    if(!colors[y]){
//printf("%d = %d\n", y, -colors[x]);
      colors[y] = -colors[x];
      if(colors[y] > 0) r++;
      else r--;
      r += color(y, x);
      if(!bipartite) return 0;
    }
    else if(colors[y] == colors[x]){
//printf("COnflict %d %d\n", x, y);
      bipartite = false;
      return 0;
    }
  }
  return r;
}

int main(){
  int i, j;
  scanf("%d%d", &n, &m);
  for(i=0;i<n;i++){
    for(j=i+1;j<n;j++) edges0.emplace(std::pair<int, int>(i, j));
  }
  for(i=0;i<m;i++){
    int x, y;
    scanf("%d%d", &x, &y);
    edges0.erase(std::minmax(x-1, y-1));
  }
  for(auto e: edges0){
    int x = e.first;
    int y = e.second;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  for(i=0;i<n;i++){
    if(!colors[i]){
//printf("NNN %d\n", i);
      colors[i] = 1;
      bipartite = true;
      cliques.push_back(std::abs(1+color(i, -1)));
      if(!bipartite){
        puts("-1");
        return 0;
      }
    }
  }
  int sum = 0;
  for(auto x: cliques){
    sum += x;
    //printf("%d\n", x);
  }
  int g = sum / 2;
  //printf("sum %d\n", sum);
  //std::sort(cliques.begin(), cliques.end(), std::greater<int>());

  int dp[701][700];
  
  for(int j=0;j<=g;j++){
    dp[0][j] = 0;
  }
  for(i=0;i<cliques.size();i++){
    for(int j=0;j<cliques[i];j++){
      dp[i+1][j] = dp[i][j];
    }
    for(int j=cliques[i];j<=g;j++){
      dp[i+1][j] = std::max(dp[i][j], cliques[i] + dp[i][j-cliques[i]]);
    }
  }

  int d = sum - 2**std::max_element(dp[i], dp[i] + g + 1);
  int x = (n+d)/2;
  int y = (n-d)/2;
// printf("d = %d\n", d);
// printf("x = %d, y = %d\n", x, y);

  printf("%d\n", x*(x-1)/2+y*(y-1)/2);
  
    
  return 0;
}


Measured memory_bytes: 14592
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; ++i)
#define FOR(i,n,m) for(long long i=n; i<m; ++i)
#define DUMP(n,a) for(long long dump=0; dump<n; ++dump) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b,c;
	cin>>a>>b>>c;
	if(a==b) cout<<c<<endl;
	if(c==b) cout<<a<<endl;
	if(a==c) cout<<b<<endl;
}


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

int main() {
  int n;
  cin >> n;
  unordered_map<string, int> mp;
  for (int i=0; i<n; i++) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    mp[s]++;
  }
  long long ans = 0;
  for (auto &p : mp) {
    int s = p.second;
    ans += (long long)s*(s-1)/2;
  }

  cout << ans << endl;
  return 0;
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

typedef array<int, 5> A;

string s, t;
A dp[3003][3003];

int main() {
	cin >> s >> t;
	s = "[" + s + "]";
	t = "[" + t + "]";
	
	dp[0][0] = { 0, 0, 0, -1, -1 };
	inc(i, s.size()) { A ma = dp[0][0];
	inc(j, t.size()) {
		setmax(ma, dp[i][j]);
		if(s[i] == t[j]) {
			dp[i + 1][j + 1] = A { ma[0] + 1, i + 1, j + 1, ma[1], ma[2] };
		} else {
			dp[i + 1][j + 1] = dp[i][j + 1];
		}
	}
	}
	
	string ans;
	int I = s.size();
	int J = t.size();
	while(true) {
		assert(s[I - 1] == t[J - 1]);
		int i = dp[I][J][3];
		int j = dp[I][J][4];
		I = i;
		J = j;
		assert(s[I - 1] == t[J - 1]);
		
		if(I == 1) { break; }
		ans += s[I - 1];
	}
	reverse(ALL(ans));
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 176384
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, MOD = map(int,input().split())
    if n == 1:
        print(1)
        return

    E = [[] for _ in range(n)]
    nv_to_idx = [{} for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        nv_to_idx[u][v] = len(E[u])
        nv_to_idx[v][u] = len(E[v])
        E[u].append(v)
        E[v].append(u)
    deg = [len(E[v]) - 1 for v in range(n)]
    deg[0] += 1

    topological_sort = []
    parent = [None] * n
    stack = [(~0, -1), (0, -1)] # (v, p)
    while stack:
        v, p = stack.pop()
        if v >= 0:
            parent[v] = p
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            if deg[~v] == 0:
                topological_sort.append(~v)
            deg[p] -= 1

    # tree DP
    dp = [None] * n
    for v in topological_sort:
        res = 1
        for nv in E[v]:
            if nv == parent[v]:
                continue
            res = res * (dp[nv] + 1) % MOD
        dp[v] = res

    # rerooting
    def rerooting(v, p):
        # rerooting を先に済ませる
        if p != -1 and v != -1:
            idx = nv_to_idx[p][v]
            p_res = 1
            if idx > 0:
                p_res *= cum_left[p][idx - 1]
            if idx < len(E[p]) - 1:
                p_res *= cum_right[p][idx + 1]
            dp[p] = p_res % MOD

        if v == -1:
            return
        # monoid に対する cumulative sum を計算
        if cum_left[v] is None:
            left = [(dp[nv] + 1) % MOD for nv in E[v]]
            right = [(dp[nv] + 1) % MOD for nv in E[v]]
            k = len(E[v])
            for i in range(k - 1):
                left[i + 1] *= left[i]
                left[i + 1] %= MOD
            for i in range(k - 1, 0, -1):
                right[i - 1] *= right[i]
                right[i - 1] %= MOD
            cum_left[v] = left
            cum_right[v] = right
        dp[v] = cum_left[v][-1]

    ans = [None] * n
    ans[0] = dp[0]
    stack = [(~0, -1), (0, -1)]
    cum_left = [None] * n
    cum_right = [None] * n
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            ans[v] = dp[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(*ans, sep = '\n')
resolve()

Measured memory_bytes: 131616
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int B = sc.nextInt();

		if ((A * B) % 2 == 0) {
			System.out.println("No");
		} else {
			System.out.println("Yes");
		}
		
	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
using bit = unsigned long long;

struct block {
  string s[2][2];
};

int h, n;
bit s;
vector<block> blocks;

int solve(int now, bit nows, int cnt);
bool valid(bit nows, bit nowf, int w) {
  return !(nows & (nowf << (4 * w)));
}
bit parse(block nowb, int x, int y);

int main() {
  while(1) {
    cin >> h >> n;
    if(h + n == 0) break;
    s = 0;
    for(int i = 0; i < h; ++i) {
      bit nows = 0;
      for(int j = 0; j < 2; ++j) {
        string str;
        cin >> str;
        for(int k = 0; k < 2; ++k)
          if(str[k] == '#') nows += 1LL << (j * 2 + k);
      }
      s += nows << i * 4;
    }
    blocks.resize(n);
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < 2; ++j)
        for(int k = 0; k < 2; ++k) cin >> blocks[i].s[j][k];
    }
    cout << solve(0, s, 0) << endl;
  }
  return 0;
}

int solve(int now, bit nows, int cnt) {
  int res = 0;
  if(now == n) return cnt;
  for(int i = -1; i <= 1; ++i)
    for(int j = -1; j <= 1; ++j) {
      bit fallb = parse(blocks[now], i, j), nexts = nows,
          nextcnt = cnt;
      if(fallb == 0) continue;
      int w = 15;
      while(valid(nexts, fallb, w) && w >= 0) --w;
      ++w;
      nexts |= (fallb << (4 * w));

      for(int k = 0; k < 16; ++k)
        if(((nexts >> (4 * k)) % 16 == 15)) {
          bit tmp = 1, tmp2;
          tmp <<= 4 * k;
          if(tmp) --tmp;
          tmp2 = tmp & nexts;
          nexts >>= 4;
          nexts = (nexts | tmp) - tmp;
          nexts += tmp2;
          ++nextcnt;
          --k;
        }
      res = max(res, solve(now + 1, nexts, nextcnt));
    }
  return res;
}

bit parse(block nowb, int x, int y) {
  int bcnt = 0, nowcnt = 0;
  bool ch = 0;
  for(int i = 0; i < 2; ++i) {
    for(int j = 0; j < 2; ++j)
      for(int k = 0; k < 2; ++k)
        if(nowb.s[i][j][k] == '#') ++bcnt;
    if(i == 0 && bcnt) ch = 1;
  }
  if(!ch) {
    swap(nowb.s[0][0], nowb.s[1][0]);
    swap(nowb.s[0][1], nowb.s[1][1]);
  }
  bit res = 0;
  for(int ud = 0; ud < 2; ++ud)
    for(int i = 0; i < 2; ++i)
      for(int j = 0; j < 2; ++j) {
        int nowx = x + i, nowy = y + j;
        if(nowx < 0 || nowx == 2 || nowy < 0 || nowy == 2 ||
           nowb.s[ud][nowx][nowy] != '#')
          continue;
        ++nowcnt;
        res += 1 << (ud * 4 + (2 * i + j));
      }
  if(nowcnt != bcnt) return 0;
  return res;
}


Measured memory_bytes: 3176
// E - Multiplication 4
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
int vpop(vector<int>& v){int x=v.back();v.pop_back();return x;}

int main(){
	int N, K; cin>>N>>K;
	vector<int> P, M;
	rep(i, N){
		int a; cin>>a;
		if(a < 0) M.push_back(a);
		else P.push_back(a);
	}

	sort(P.begin(), P.end());
	sort(M.rbegin(), M.rend());

	vector<int> p, m;
	while(int(p.size() + m.size()) < K){
		if(P.size() > 0 && M.size() <= 0) p.push_back(vpop(P));
		else if(P.size() <= 0 && M.size() > 0) m.push_back(vpop(M));
		else if(P.back() < -M.back()) m.push_back(vpop(M));
		else p.push_back(vpop(P));
	}

	if(m.size()%2){
		int mi, pi;
		mi = (p.size() * M.size() == 0)? 1: vpop(M);
		pi = (m.size() * P.size() == 0)? -1: vpop(P);
		if(mi < 0 && pi >=0){
			if(abs((ll)p.back() * pi) < abs((ll)m.back() * mi)){ p.pop_back(); m.push_back(mi); }
			else{ m.pop_back(); p.push_back(pi); }
		}
		else if (mi < 0){ p.pop_back(); m.push_back(mi); }
		else if (pi >= 0){ m.pop_back(); p.push_back(pi); }
		else{
			while(m.size() > 0) p.push_back(vpop(m));
			while(P.size() > 0) p.push_back(vpop(P));
			while(M.size() > 0) p.push_back(vpop(M));
			sort(p.begin(), p.end(), [](int x, int y){ return abs(x) < abs(y); });
			while((int)p.size() > K) p.pop_back();
		}
	}

	ll ans = 1;
	int mod = 1'000'000'007;
	for(int a:p) ans = ans * a % mod;
	for(int a:m) ans = ans * a % mod;
	cout<< (ans+mod)%mod <<endl;
}


Measured memory_bytes: 5780
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<set>
#include <valarray>
#include<stack>
#include<sstream>
#include<math.h>
 
using namespace std;
 
void Solution()
{
    string s;
    getline(cin, s);  //for input
    string outPut = "";
    
    for (int i=0; i < (int)s.size(); i++) 
    {
        if (isalpha(s[i])) {   //function for checking if s[i] is alphabet
            
            if (islower(s[i]))
            {
                outPut += toupper(s[i]);  //lower change to upper
            } 
            else if (isupper(s[i])) 
            {
                outPut += tolower(s[i]); //upper change to lower
            }
        } 
        else //if string is ',' '.'
        {
            outPut += s[i];
        }
    }
    
    cout << outPut << endl;   
}
 
int main()
{
    Solution();
    return 0;
}

Measured memory_bytes: 1196
import std;

alias sread = () => readln.chomp();
alias lread = () => readln.chomp.to!long();
alias aryread(T = long) = () => readln.split.to!(T[]);

void main()
{
    auto n = lread();
    auto h = aryread();
    // writeln(h);
    // writeln(h.maxElement);
    long cnt;
    while (true)
    {
        if (h.maxElement == 0)
        {
            break;
        }
        long i;
        while (i < n)
        {
            if (h[i] == 0)
            {
                i += 1;
            }
            else
            {
                cnt += 1;
                while ((i < n) && (h[i] > 0))
                {
                    h[i] -= 1;
                    i += 1;
                }
            }

        }
    }
    writeln(cnt);

}

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
vector<ll> ad[100005];
ll dp[100005];

ll dfs(ll i) {
    if(dp[i] != -1) return dp[i];
    bool leaf = 1;
    ll best = 0;
    for(auto x: ad[i]) {
        leaf = 0;
        best = max(best, dfs(x));
    }
    return dp[i] = leaf ? 0 : 1 + best;
}

int main() {
    ll n, m;
    cin >> n >> m;
    ll x, y;
    memset(dp, -1, sizeof dp);
    for(int i = 0; i < m; ++i) {
        cin >> x >> y;
        ad[x].push_back(y);
    }
    ll ans = INT_MIN;
    for(int i = 1; i <= n; ++i) {
        ans = max(ans, dfs(i));
    }
    cout << ans;
}


Measured memory_bytes: 11864
#include <iostream>
void p(int a, int b, int c) {
    std::cout << a << ' ' << b << ' ' << c << std::endl;
}
int main() {
    int a, b, c;
    std::cin >> a >> b >> c;
    if (a > b) {
        if (b > c) {
            p(c, b, a);
        } else {
            if (a > c) {
                p(b, c, a);
            } else {
                p(b, a, c);
            }
        }
    } else {
        if (b > c) {
            if (a > c) {
                p(c, a, b);
            } else {
                p(a, c, b);
            }
        } else {
            p(a, b, c);
        }
    }
}



Measured memory_bytes: 3100
#include<iostream>
#include<string>
#include<map>
#include<algorithm>

int main(void){
    int n;
    std::cin >> n;

    std::map<std::string, int> mp;

    for(int i = 0; i < n; i++){
        std::string s;
        std::cin >> s;
        std::sort(s.begin(), s.end());
        mp[s]++;
    }
    
    long long ans = 0;
    for(auto &p : mp){
        int temp = p.second;
        ans += (long long) temp * (temp - 1) / 2;
    }
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
#define MOD 1000000007

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline T gcd(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T lcm(T a,T b){return a*b/gcd(a,b);}

const int INF=1e9;
const double eps=0.0000000001;

ll n;

ll dfs(ll a){
  if(a>n)return 0;
  bool c[4]={0};
  ll i=0;
  string s=to_string(a);
  FOR(i,s.length()){
    if(s[i]=='3')c[0]=1;
    else if(s[i]=='5')c[1]=1;
    else if(s[i]=='7')c[2]=1;
    else c[3]=1;
  }
  if(c[0] && c[1] && c[2] && !c[3]){
    i++;
  }
  i+=dfs(a*10+3);
  i+=dfs(a*10+5);
  i+=dfs(a*10+7);
  return i;
}




int main(){
  cin >> n;
  cout << dfs(0) << endl;
}


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

#define   ll    long long int

const ll mod = 998244353;
ll dis[100005];

ll bigmod(ll a, ll b, ll mod)
{
    if (b == 0) return 1;
    ll x = bigmod(a, b / 2, mod);
    x = (x * x) % mod;
    if (b % 2 == 1) x = (x * a) % mod;
    return x;
}

int main( )
{
    ll n, i, j, k;
    ll ans = 1;
    cin >> n;
    cin >> j;
    if (j != 0)
    {
        cout << "0\n";
        return 0;
    }
    dis[0]++;
    for (i = 2; i <= n; i++)
    {
        cin >> j;
        dis[j]++;
    }
    if (dis[0] != 1)
    {
        cout << "0\n";
        return 0;
    }
    for (i = 1; i < n; i++)
    {
        if (dis[i] == 0) break;
        ans = (ans * bigmod(dis[i - 1], dis[i], mod)) % mod;
    }
    for ( ; i < n; i++)
    {
        if (dis[i] != 0)
        {
            cout << "0\n";
            return 0;
        }
    }
    cout << ans << '\n';
    return 0;
}


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

  vector<int> B(N-1);
  REP(i, N-1) cin >> B[i];
  
  vector<int> A(N);

  for(int i = N-2;i > 0;i--){
    if(B.at(i)>=B.at(i-1)){
      A.at(i) = B.at(i-1);
    }else{
      A.at(i) = B.at(i);
    }
  }
  A.at(0) = B.at(0);
  A.at(N-1) = B.at(N-2);

  int sum = 0;
  REP(i,N){
    sum+=A.at(i);
  }

  cout << sum << endl;
}

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

 
int main()
{
    int N;
    cin >> N;
    string S[N];
    int ans[4];
    string variety[4] = {"AC", "WA", "TLE", "RE"};
    for (int n=0; n<4; n++) {
        ans[n] = 0;
    }
    for (int n=0; n<N; n++) {
        cin >> S[n];
        if (S[n]=="AC") {
            ans[0] += 1;
        }
        if (S[n]=="WA") {
            ans[1] += 1;
        }
        if (S[n]=="TLE") {
            ans[2] += 1;
        }
        if (S[n]=="RE") {
            ans[3] += 1;
        }
    }
    for (int n=0; n<4; n++) {
        cout << variety[n] + " x " + to_string(ans[n]) << endl;
    }
    
}

Measured memory_bytes: 6848
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n , k , INF = 1e9+5;
    cin >> n >> k;
    vector<int> h(n+1);
    for(int i = 1 ; i <= n ; i++) cin >> h[i];
    // vector<int > h(n);
    // for(int &i : h) cin >> i;

    vector<int> dp(n+1,INF);
    dp[1] = 0;
    dp[2] = abs(h[2] - h[1]);
    for(int i = 3 ; i<=n ; i++)
        for(int j = 1; j <= k && i-j >= 1; j++) 
            dp[i] = min( dp[i] , dp[i-j] + abs(h[i] - h[i-j]));
    
    cout <<dp[n];


    return 0;
}

Measured memory_bytes: 4040
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
import copy
import itertools
n = int(readline())

lst1 = [i for i in range(1,n+1)]
lst2 = copy.deepcopy(lst1)
lst3 = copy.deepcopy(lst1)

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
ans = 0
for i,j,k in itertools.product(lst1,lst2,lst3):
    ans += gcd(i,gcd(j,k))
print(ans)

Measured memory_bytes: 80712
n, m  = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
sumer = sum(a)
ans = 0
for i in a:
    if i >= sumer / (4 * m):
        ans += 1

if ans >= m:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 40492
#include<iostream>
#include<vector>
#include<cassert>
#include<cmath>

using namespace std;
int n, m;

vector<vector<int>> g;
bool visited[100100];
void dfs(int node, int from) {
    visited[node] = true;
    for (int to : g[node]) {
        if (to == from) continue;
        if (visited[to]) continue;
        dfs(to, node);
    }
}

int main()
{
    cin >> n >> m;
    fill(visited, visited + n, false);
    g = vector<vector<int>>(n, vector<int>());
    for (int i = 0; i < m; ++i) {
        int from, to, trash;
        cin >> from >> to >> trash;
        from--;
        to--;
        g[from].push_back(to);
        g[to].push_back(from);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;
        dfs(i, -1);
        ans++;
        // if (dfs(i, -1)) ans++;
    }
    cout << ans << endl;
}



Measured memory_bytes: 10496
#include<iostream>
using namespace std;
int main(){
    int a;
    cin >> a;
    if(a>=400&&a<=599){
        cout << 8;
    }else if(a>=600&&a<=799){
        cout << 7;
    }else if(a>=800&&a<=999){
        cout << 6;
    }else if(a>=1000&&a<=1199){
        cout << 5;
    }else if(a>=1200&&a<=1399){
        cout << 4;
    }else if(a>=1400&&a<=1599){
        cout << 3;
    }else if(a>=1600&&a<=1799){
        cout << 2;
    }else if(a>=1800&&a<=1999){
        cout << 1;
    }
    return 0;

}

Measured memory_bytes: 3600
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<list>
using namespace std;

typedef long long ll;

#define MOD 1000000007

class Comb{
private:
  ll *fac,*finv,*inv;
public:
  Comb(){
    fac = new ll[1000000];
    finv = new ll[1000000];
    inv = new ll[1000000];
    fac[0] = 1;
    for(int i=1;i<1000000;i++){
      fac[i] = i*fac[i-1];
      fac[i] %= MOD;
    }
    inv[1] = 1;
    for(int i=2;i<1000000;i++){
      inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD;
    }
    finv[0] = 1;
    for(int i=1;i<1000000;i++){
      finv[i] = inv[i]*finv[i-1];
      finv[i] %= MOD;
    }
  }
  ll calc(ll n,ll k){
    ll c = fac[n];
    c *= finv[k];c %= MOD;
    c *= finv[n-k];c %= MOD;
    return c;
  }
};

ll gcd(ll x,ll y){
  if(x%y == 0) return y;
  else return gcd(y,x%y);
}

int main(){
  int n,k;
  cin >> n >> k;
  vector<double> p(n);
  for(int i=0;i<n;i++){
    cin >> p[i];
    p[i] = (p[i]*(p[i]+1))/2*(1/(p[i]+0.0));
  }
  double ans = 0.0;
  for(int i=0;i<k;i++){
    ans += p[i];
  }
  double temp;
  temp = ans;
  for(int i=0;i<n-k;i++){
    temp -= p[i];
    temp += p[k+i];
    ans = max(ans,temp);
  }
  cout << setprecision(12) << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
def get_int
  gets.chop.to_i
end

def get_ints
  gets.chop.split.map(&:to_i)
end

def get_double
  gets.chop.to_f
end

def get_str
  gets.chop
end

def get_strs
  gets.chop.split
end

def main
  n = get_int
  ds = get_ints
  if ds[0] != 0
    puts 0
    exit 0
  end
  ds_with_i = ds.map.with_index.to_a
  ds_with_i.sort_by! {|e| e[0] }
  branch = Hash.new(0)
  ans = 1
  found_zero = false
  ds_with_i.each do |d, i|
    if d == 0
      if not found_zero
        branch[0] = 1
        found_zero = true
      else
        puts 0
        exit 0
      end
    else
      m = branch[d-1]
      ans *= m
      ans = ans % 998244353
      branch[d] += 1
    end
  end
  puts ans
end

if __FILE__ == $0
  main
end




Measured memory_bytes: 20936
#include<bits/stdc++.h>
#define int long long
#define out(x) cerr << #x << " = " << x << "\n"
using namespace std;
// by piano
template<typename tp> inline void read(tp &x) {
	x = 0;char c = getchar();bool f = 0;
	for(; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
	for(; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
	if(f) x = -x;
}
const int N = 310, mo = 1e9  + 7;

struct P {
	int l, r, x;
	inline void in() {
		read(l), read(r), read(x);
	}
};
vector<P> vec[N];
int f[N][N][N];
int n, m, ans = 0;

inline int C(int r, int g, int b) {
	int p = max(r, max(g, b));
	for(vector<P> :: iterator u = vec[p].begin(); u != vec[p].end(); ++ u) {
		int cnt = 0;
		if(r >= u -> l) cnt ++;
		if(g >= u -> l) cnt ++;
		if(b >= u -> l) cnt ++;
		if(cnt != u -> x) return 0;
	}
	return 1;
}
inline void U(int &a, int b) {
	for(a += b; a >= mo; a -= mo);
}
main() {
//	freopen("1.txt", "w", stdout);
	read(n);read(m);
	for(int i = 1; i <= m; i ++) {
		int l, r, x;
		read(l);
		read(r);
		read(x);
		vec[r].push_back(P{l, r, x});
	}
	f[0][0][0] = 1;
	for(int r = 0; r <= n; r ++) {
		for(int g = 0; g <= n; g ++) {
			for(int b = 0; b <= n; b ++) {
				int &v = f[r][g][b];
				if(v == 0) continue;
				if(!C(r, g, b)) {
					v = 0;
					continue;
				}
				int p = max(r, max(g, b)) + 1;
				U(f[p][g][b], v);
				U(f[r][p][b], v);
				U(f[r][g][p], v);
			}
		}
	}
	for(int r = 0; r <= n; r ++) {
		for(int g = 0; g <= n; g ++) {
				U(ans ,f[r][g][n]);
//				cout << r << ' ' << g << ' ' << b << ' ' << f[r][g][b] << "\n";
		}
	}
	for(int r = 0; r <= n; r ++) {
		for(int g = 0; g <= n; g ++) {
				U(ans ,f[r][n][g]);
//				cout << r << ' ' << g << ' ' << b << ' ' << f[r][g][b] << "\n";
		}
	}
	for(int r = 0; r <= n; r ++) {
		for(int g = 0; g <= n; g ++) {
				U(ans ,f[n][r][g]);
//				cout << r << ' ' << g << ' ' << b << ' ' << f[r][g][b] << "\n";
		}
	}
	cout << ans << "\n";
	return 0;
}

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

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

	int n = s.size();
	vector<int> ans(n);
	int cntR = 0, cntL = 0;
	rep(i, 0, n) {
		if (s[i] == 'L') {
			while (i <= n - 1 && s[i] == 'L') {
				cntL++; i++;
			}
			int p = (cntR + cntL) / 2;
			int k = i - cntL;
			if ((cntR - cntL) % 2 == 0) {
				ans[k - 1] = p; ans[k] = p;
			}
			else {
				if (cntL % 2 == 1) {
					ans[k - 1] = p; ans[k] = p + 1;
				}
				else {
					ans[k - 1] = p + 1; ans[k] = p;
				}	
			}
			cntR = 0; cntL = 0; i--;
		}
		else cntR++;
	}

	rep(i, 0, n) {
		if (i > 0) cout << " ";
		cout << ans[i];
	}
	cout << endl;

	return 0;
}

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

int main() {
  int N, M, R;
  cin >> N >> M >> R;
  vector<int> r(R);
  for (int i = 0; i < R; i++) {
    cin >> r.at(i);
    r.at(i)--;
  }

  vector<vector<int>> G(N, vector<int>(N, 1e9));
  for (int i = 0; i < N; i++) {
    G.at(i).at(i) = 0;
  }
  for (int a, b, c; cin >> a >> b >> c;) {
    G.at(--a).at(--b) = c, G.at(b).at(a) = c;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        G.at(j).at(k) = min(G.at(j).at(k), G.at(j).at(i) + G.at(i).at(k));
      }
    }
  }

  int ans = 1e9;
  sort(r.begin(), r.end());
  do {
    int tmp = 0;
    for (int i = 0; i + 1 < R; i++) {
      tmp += G.at(r.at(i)).at(r.at(i + 1));
    }
    ans = min(ans, tmp);
  } while (next_permutation(r.begin(), r.end()));
  cout << ans << "\n";
}

Measured memory_bytes: 384
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
dist = [[] for i in range(N)]
edge = {}
for i in range(N - 1):
    a, b = getNM()
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)
    # queryの何番目のエッジか
    edge[(a - 1, b - 1)] = i
    edge[(b - 1, a - 1)] = i

ignore = [-1] * N
ignore[0] = 0
ans = [0] * (N - 1)

pos = deque([0])
while len(pos) > 0:
    u = pos.popleft()
    j = 1
    for i in dist[u]:
        if ignore[i] < 0:
            if j == ignore[u]:
                j += 1
            ignore[i] = j
            ans[edge[(i, u)]] = j
            pos.append(i)
            j += 1
print(max(ans))
for i in ans:
    print(i)

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

char A[1000];

char is[1000][1000];
int plu[1000];

using namespace std;

int main(){
    int N, M, i ,j, cnt = 0;
    char c;
    scanf("%d",&N);
    scanf("%c",&c);

    for(i=0;i<N;i++){

        scanf("%s",A);
        scanf("%c",&c);
        for(j=0;j<cnt;j++){
            if(strcmp(A,is[j]) == 0){
                plu[j]++;
                break;
            }
        }
        if(j == cnt){
            strcpy(is[cnt],A);
            plu[cnt]++; cnt++;
        }
    }
    scanf("%d",&M);
    scanf("%c",&c);

    for(i=0;i<M;i++){
        scanf("%s",A);
        scanf("%c",&c);
        for(j=0;j<cnt;j++){
            if(strcmp(A,is[j]) == 0){
                plu[j]--;
                break;
            }
        }
        if(j == cnt){
            strcpy(is[cnt],A);
            plu[cnt]--; cnt++;
        }
    }

    int ma = -987654321;

    for(i=0;i<cnt;i++) ma = max(plu[i],ma);
    printf("%d",max(ma,0));

    return 0;
}


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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var maxIndex = int.Parse(Console.ReadLine());
            var list = Console.ReadLine().Split().Select(x => int.Parse(x)).ToList();
            var index = 2;
            int cnt = 0;
            while (index < maxIndex)
            {
                if (IsMedian(list[index - 1], new int[3] { list[index - 2], list[index - 1], list[index] }))
                {
                    cnt++;
                }
                index++;
            }

            Console.WriteLine(cnt);
        }

        private static bool IsMedian(int medianVal, int[] list)
        {
            var isMax = list.Max() != medianVal;
            var isMin = list.Min() != medianVal;

            return isMax && isMin;
        }

    }
}

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

#define N 200200

int n, K, p[N], nxt[N], prv[N];
bool vis[N];

int main() {
    cin >> n >> K;
    for (int i = 1; i <= n; i ++) cin >> p[i], p[i] ++;
    p[0] = n + 1;
    for (int i = 1; i <= n; i ++) {
        prv[i] = i - 1;
        while (p[prv[i]] < p[i]) prv[i] = prv[prv[i]];
    }
    for (int i = n; i; i --) {
        nxt[i] = i + 1;
        while (p[nxt[i]] > p[i]) nxt[i] = nxt[nxt[i]];
    }
    int ans = 0;
    for (int i = 1, j = 1; i <= n; i = j) {
        for (j ++; j <= n && p[j] > p[j-1]; j ++);
        for (int k = i; k + K <= j; k ++) vis[k] = ans = 1;
    }
    for (int i = 1, j; i <= n - K + 1; i ++) if (!vis[i]) {
        for (j = i; j <= n - K + 1; j ++) {
            if (vis[j] || nxt[j] <= j + K || prv[j+K] >= j) break;
        }
        ans ++; i = j;
    }
    cout << ans << endl;
}


Measured memory_bytes: 2816