akhauriyash/Code-Regression huggingface dataset:
# 本当はBITやセグメントツリーを用いた解法を使いたいところ...(理解不足)

import bisect
from collections import defaultdict

N = int(input())
# 書き換える時に文字列だと不便なのでリスト化しておく
S = list(input())
Q = int(input())

# setは順序を保証しない、setで管理するとクエリ2で（リスト化した後に）ソートする必要がある
# 最初からlistで管理して、クエリ1ではソート済になるように挿入する
dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        # 書き換える必要がない場合
        if S[b] == c:
            continue
        else:
            # クエリ2が飛んできた時に毎回ソートしていては間に合わない
            # クエリ1の時点でソート済にしておく
            # 二分探索の際、同じ数字が既にあることはないので、leftでもrightでも良い
            dict[S[b]].remove(b)
            idx = bisect.bisect(dict[c], b)
            dict[c].insert(idx, b)
            # 文字列の書き換え
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        # 文字が何種類あるか
        char_cnt = 0
        for key, value in dict.items():
            # left,rightを指定する必要がある
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_cnt += 1
        ans.append(char_cnt)

for i in ans:
    print(i)


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

int main(){
  int n;
  cin >> n;
  int t[101];
  int v[102];
  for (int i = 0; i < n; i++){
    scanf("%d", &t[i]);
  }
  for (int i = 0; i < n; i++){
    scanf("%d", &v[i]);
  }
  v[n] = 0;
  float g[60001];
  g[0] = 0;
  int tt = 0;
  for (int i = 0; i < n; i++){
    int u = tt + t[i] * 2;
    for (; tt < u; tt++){
      if (g[tt] + 0.5 <= v[i]) {
        g[tt+1] = g[tt] + 0.5;
      }
      else g[tt+1] = g[tt];
    }
    if (g[tt] > v[i+1]) {
      int p = tt;
      g[p] = v[i+1];
      while (true) {
        if (g[p-1] != g[p] + 0.5){
          g[p-1] = g[p] + 0.5;
          p--;
        } else break;
      }
    }
  }

  float ans = 0;
  for (int i = 0; i < tt; i++){
    ans += (g[i] + g[i+1]);
  }

  printf("%.8f\n", ans / 4);

  return 0;
}


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

using namespace std;
using ll = long long;

int H, W;
char S[21][21];

int bfs(int sh, int sw) {
    int d[21][21];
    memset(d, -1, sizeof(d));
    d[sh][sw] = 0;
    int dh[] = {1, -1, 0, 0};
    int dw[] = {0, 0, 1, -1};

    queue<pair<int, int>> Q;
    Q.push(make_pair(sh, sw));

    int max_dist = 0;
    while (Q.size()) {
        auto p = Q.front();
        Q.pop();
        int h = p.first;
        int w = p.second;
        for (int i = 0; i < 4; ++i) {
            int nh = h + dh[i];
            int nw = w + dw[i];
            if (nh < 0 || nh >= H || nw < 0 || nw >= W)
                continue;
            if (d[nh][nw] != -1)
                continue;
            if (S[nh][nw] == '#')
                continue;
            d[nh][nw] = d[h][w] + 1;
            max_dist = max(max_dist, d[nh][nw]);
            Q.push(make_pair(nh, nw));
        }
    }

    return max_dist;
}

int main() {
    cin >> H >> W;

    for (int h = 0; h < H; ++h)
        for (int w = 0; w < W; ++w) {
            cin >> S[h][w];
        }

    int ans = 0;
    for (int h = 0; h < H; ++h)
        for (int w = 0; w < W; ++w) {
            if (S[h][w] == '.')
                ans = max(ans, bfs(h, w));
        }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<algorithm>

using namespace std;

int main(){
    int N;
    map<string, bool> T;
    cin >> N;
    for (int i = 0; i < N; i++) {
        char s[16],t[16];
        scanf("%s %s",s,t);
        if (s[0] == 'i') {
            T[t] = true;
        }else{
            if (T[t]) printf("yes\n");
            else printf("no\n");
        }
    }
    
    
    return 0;
}

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

int main() {
	ios_base::sync_with_stdio( false );

	int N, K;
	cin >> N >> K;

	priority_queue<int> l;
	for( int i = 0; i < N; ++i ) {
		int x;
		cin >> x;
		l.push( x );
	}

	int result = 0;
	for( int i = 0; i < K; ++i ) {
		result += l.top();
		l.pop();
	}

	cout << result << endl;

	return 0;
}


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

using namespace std;

int main() {
    int n;
    int a[110]; 
    int ans = 0;

    for (int i = 0; i < 110; i++){ 
        a[i] = 0;
    }
    cin >> n;
    for (int i = 0; i < n; i++){ 
        cin >> a[i];
    }
    sort(a, a + n, greater<int>());
    for (int i = 0; i < n; i+=2){
        ans += (a[i]-a[i+1]);
    }

    cout << ans << "\n";
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e+18
#define int long long
using namespace std;

signed main(){
	int n,m,x,y,xmax = -INF,ymin = INF;
	cin >> n >> m >> x >> y;
	for(int i = 0;i < n;i++){
		int t;
		cin >> t;
		xmax = max(xmax,t);
	}
	for(int i = 0;i < m;i++){
		int t;
		cin >> t;
		ymin = min(ymin,t);
	}
	bool flag = false;
	for(int i = xmax + 1;i <= ymin;i++){
		if(x < i && i <= y) flag = true;
	}
	if(flag) cout << "No War" << endl;
	else cout << "War" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int findsum(int n)
{
    int sum = 0;
    while(n>0){
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
int main(void)
{
    int N;
    scanf("%d", &N);
    puts(N % findsum(N) == 0?"Yes":"No");
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <cstdio>
#include <unordered_set>
inline int getInt(){ int s; scanf("%d", &s); return s; }

using namespace std;

int main(){
  const int n = getInt();
  const int m = getInt();

  std::unordered_set<int> s;
  vector<int> v(n);

  REP(i,n) v[i] = getInt();
  reverse(v.begin(), v.end());

  for(int i = 0; i < n; i++){
    if((int) s.size() < m && s.count(v[i]) == 0){
      printf("%d\n", v[i]);
      s.insert(v[i]);
    }
  }

  return 0;
}

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

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;

ll N, M;
ll A[100010];
priority_queue<ll> pq;
ll ans;
int main(){
	cin >> N >> M;
	REP(i,0,N){
		ll a;
		cin >> a;
		pq.push(a);
	}
	REP(i,0,M){
		ll now=pq.top();
		pq.pop();
		pq.push(now/2);
	}
	while(!pq.empty()){
		ans += pq.top();
		pq.pop();
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
/* this code is generated by shikhar verma . Dont try to copy it. You may be booked under plaigarism. */
int numberofPaths(int h,int w,int a,int b);
int main()
{
    ll n,i,j,len1,a,b,h,w,t;
   /* freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);*/
	vector <int> v;
	string s;
	cin>>s;
	for(i=0;i<s.size();i++)
    {
        if(s[i]!='B')
        {
            v.push_back(s[i]-'0');
        }
        else{
                if(!v.empty())
                    v.pop_back();
                else    continue;
        }
    }
    for(i=0;i<v.size();i++)
    {
        cout<<v[i];
    }



    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
const int maxn=1e5+5;
int n,a[maxn],b[maxn],c[maxn];
inline void init(){
	n=read();
	for (int i=1;i<=n;i++){
		a[i]=read();
	}
	for (int i=1;i<=n;i++){
		b[i]=read();
	}
	for (int i=1;i<=n;i++){
		c[i]=read();
	}
}
const int inf=1e9;
typedef long long ll;
ll s[maxn],sum[maxn];
inline void solve(){
	sort(a+1,a+1+n); a[n+1]=b[n+1]=c[n+1]=inf;
	sort(b+1,b+1+n);
	sort(c+1,c+1+n);
	int pos=1;
	for (int i=1;i<=n;i++){
		while (pos<=n&&c[pos]<=b[i]){
			pos++;
		}
		s[i]=n-pos+1;
	}
	for (int i=n;i;i--){
		sum[i]=sum[i+1]+s[i];
	}
	pos=1; ll ans=0;
	for (int i=1;i<=n;i++){
		while (pos<=n&&b[pos]<=a[i]){
			pos++;
		}
		ans+=sum[pos];
	}
	printf("%lld\n",ans);
}
int main(){
	init();
	solve();
	return 0;
}

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

int main() {
	string a,b;
	int c=0;
	cin >> a >> b;
	
	for (int i = 0; i < 3;i++) {
		if (a[i]== b[i])
			c++;
	}
	cout << c << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline


def read():
    S = input().strip()
    return S,


def solve(S):
    N = len(S)
    for i in range(N // 2 - 1, 0, -1):
        a0 = 0
        a1 = i
        b0 = i
        b1 = i + i
        if S[a0:a1] == S[b0:b1]:
            return b1
    return 0


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SORT(i) sort((i).begin(),(i).end())
constexpr int INF = 2000000000;
constexpr int mod = 1000000007;

int main() {
	int N; cin >> N;
	if (N < 1000)puts("ABC");
	else puts("ABD");

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std;
int main(){
    double x1,x2,y1,y2,takasa,yoko,kyori,takasa2,yoko2,goukei;
    cin>>x1>>y1>>x2>>y2;
    takasa=y2-y1;
    yoko=x2-x1;
    takasa2=takasa*takasa;
    yoko2=yoko*yoko;
    goukei=takasa2+yoko2;
    kyori=sqrt(goukei);
    printf("%f",kyori);
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3196
/n,a,b=gets.split.map(&:to_i)/
/.sort/
/S = gets.chomp.chars/
a=gets.to_i
b=gets.to_i
c=gets.to_i
d=gets.to_i
e=gets.to_i
k=gets.to_i
count=0
if(e-a>k||e-b>k||e-c>k||e-d>k)
  puts ":("
else
  puts "Yay!"
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
              
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define int ll
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

using namespace std;

const int maxn = (int)1e5 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 

#define inf mod

typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        


int n, W, w[maxn], v[maxn], dp[111][maxn];           
int calc(int pos, int sum){
  if(sum > W) return -inf * inf;
  if(pos == n + 1) return 0;
  int &res = dp[pos][sum];
  if(res != -1) return res;
  res = 0;
  res = max(calc(pos + 1, sum), calc(pos + 1, sum + w[pos]) + v[pos]);
  return res;
}
main () {
  cin >> n >> W;
  forn(i, 1, n) cin >> w[i] >> v[i];
  memset(dp, -1, sizeof(dp));
  cout << calc(1, 0);
}


Measured memory_bytes: 88320
N = int(input())
B = list(map(int, input().split()))

A = [0] * N
A[0] = B[0]

for ix in range(0, N-2):
    if B[ix] < B[ix+1]:
        A[ix+1] = B[ix]
    else:
        A[ix+1] = B[ix+1]

A[-1] = B[-1]

print(sum(A))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vector< ll > >;
using pi = pair<ll,ll>;
using st = set<ll>;
using kiwi = queue<ll>;
using mp = map<ll,ll>;
using ump = unordered_map<ll,ll>;
#define MOD 1000000007
const ll mx = 1e5+123;
#define REP(i,n) for (ll i=1;i<=n;++i)
ll ax[mx];
inline bool isPeak(ll i){
    return (ax[i]>ax[i-1]&&ax[i]>ax[i+1]);
}
inline bool isValley(ll i){
    return (ax[i]<ax[i-1]&&ax[i]<ax[i+1]);
}
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main(){
    fastio;
    ll a, b, c; cin>>a>>b>>c;
    if(a%c==0)
        cout<<(b/c) - (a/c) +1<<endl;
    else
    cout<<(b/c)-(a/c)<<endl;
return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;



int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int Q;
    string s,t;
    cin>>s>>t>>Q;
    
    int S[100009], T[100009];
    //mem(S,0); mem(T,0);
    S[0]=T[0]=0;
    rep1(i,s.size()) S[i]=(s[i-1]=='A'?1:-1);
    rep1(i,t.size()) T[i]=(t[i-1]=='A'?1:-1);
    rep1(i,s.size()) S[i]+=S[i-1];
    rep1(i,t.size()) T[i]+=T[i-1];
    
    rep(i,Q){
        int a,b,c,d; cin>>a>>b>>c>>d;
        int snum = S[b]-S[a-1];
        int tnum = T[d]-T[c-1];
        int dif = snum-tnum;
        cout1((dif%3?"NO":"YES"));
    }
}

Measured memory_bytes: 1744
N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list.append(w)
    v_list.append(v)

dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if j >= w_list[i-1]:
            dp[i][j] = max(dp[i-1][j], v_list[i-1]+dp[i-1][j-w_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i])    

print(dp[N][W])

Measured memory_bytes: 147340
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;
const int MOD = 1000000007;
const double pi = acos(-1);

ll disit_sum(ll N) {
    ll ans = 0;
    while(N > 0) {
        ans += N%10;
        N /= 10;
    }
    return ans;
}

int main() {
    ll N; cin >> N;
    ll ans = disit_sum(N);

    ll deg;
    ll ex = 1;
    ll now = N;
    while(1) {
        deg = (now/ex)%10;
        now = now - (deg+1)*ex;
        //cout << now << endl;
        if(now <= 0) break;
        chmax(ans,disit_sum(now));

        ex *= 10;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3604
s = gets.chomp

n = s.length
counts = Array.new(n, 1)

(n-2).times do |i|
  if s[i] == 'R' && s[i+1] == 'R'
    counts[i+2] += counts[i]
    counts[i] = 0
  end
end

(n-2).times do |i|
  if s[-1-i] == 'L' && s[-1-(i+1)] == 'L'
    counts[-1-(i+2)] += counts[-1-i]
    counts[-1-i] = 0
  end
end

puts(counts.join(' '))

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

int main() {
   int a,b;
    cin >> a >> b;
    
    bool x = false;
  int ans = 0;
    
    rep(i,1005) {
     int za = i*8/100;
     int zb = i*10/100;
     
        if(a == za && b == zb){
           x = true;
           ans = i;
            break;
        }
        
     }
    if(x) {
        cout << ans;
          }
    else {
    cout << -1;
    }
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 300010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
double dp[310][310][310];
int used[310][310][310];
int C[3];

double loop(int a, int b, int c) {
	if(used[a][b][c]) return dp[a][b][c];
	if(a == 0 && b == 0 && c == 0) return 0.0;
	used[a][b][c] = 1;
	double res = 0;
	res += 1.0;
	if(a) res += 1.0 * a / N * loop(a - 1, b, c);
	if(b) res += 1.0 * b / N * loop(a + 1, b - 1, c);
	if(c) res += 1.0 * c / N * loop(a, b + 1, c - 1);
	// debug(a, b, c, 1.0 * N / (a + b + c) * res);
	return dp[a][b][c] = 1.0 * N / (a + b + c) * res;
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		int a; cin >> a; a--;
		C[a]++;
	}
	cout << loop(C[0], C[1], C[2]) << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



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

bool r[5][5];
bool t[5];
int f[200];
int a, b, pf = 1;

int main() {
	for (int i = 1; i <= 3; i++) {
		cin >> a >> b;
		r[a][b] = true;
		r[b][a] = true;
	}
	int i = 1;
	for (int j = 1; j <= 4; j++) {
		if (r[i][j] && i != j && (!t[i]||!t[j]) ) {
			f[pf++] = i;
			t[i] = true;
			t[j] = true;
			bool flg = true;
			for (int k = 1; k < pf; k++) {
				if (j == f[k]) flg = false;
			}
			if (flg) i = j;
			j = 1;
		}
	}
	for (int i = 1; i <= 4; i++) {
		if (!t[i]) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){ 
		Scanner sc = new Scanner(System.in);
      	//N個の都市
		int N = sc.nextInt();
      	//M本の道路
        int M = sc.nextInt();
      	//数字の組み合わせ入力
      	int Road[] = new int[N];
      	for(int i = 0;i < M * 2;i++){
		  Road[sc.nextInt()-1] += 1;
        }
      	for(int i = 0;i < N; i++){
          System.out.println(Road[i]); 
        }
    }
}

Measured memory_bytes: 35840
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
long long dp[110][110][110][2];
long long f1[110][110][110],f2[110][110][110];
long long g1[110][110][110],g2[110][110][110];
long long C[110][110];
long long Mod;
long long fpow(long long a,long long b)
{
	long long ans=1,t=a;
	while(b)
	{
		if(b&1)ans=ans*t%Mod;
		t=t*t%Mod;
		b>>=1;
	}
	return ans;
}
int main()
{
	int n,m,k;
	scanf("%d %d %d %lld",&n,&m,&k,&Mod);
	for(int i=0;i<=max(n,m);i++)
		C[i][0]=C[i][i]=1;
	for(int i=2;i<=max(n,m);i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
	for(int p=1;p<=k;p++)
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
			{
				f1[p][i][j]=fpow((fpow(p,j)-fpow(p-1,j)+Mod)%Mod,i);
				f2[p][i][j]=fpow(fpow(p,i),j);
				g1[p][i][j]=fpow(fpow(k-p+1,i),j);
				g2[p][i][j]=fpow((fpow(k-p+1,i)-fpow(k-p,i)+Mod)%Mod,j);
			}
	dp[0][0][0][1]=1;
	for(int p=1;p<=k;p++)
	{
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
			{
				if(!dp[p-1][i][j][1])continue;
				for(int q=0;q<=n-i;q++)
					dp[p][i+q][j][0]=(dp[p][i+q][j][0]+
							dp[p-1][i][j][1]*C[n-i][q]%Mod
							*f1[p][q][m-j]%Mod*g1[p][q][j])%Mod;
			}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
			{
				if(!dp[p][i][j][0])continue;
				for(int q=0;q<=m-j;q++)
					dp[p][i][j+q][1]=(dp[p][i][j+q][1]+
							dp[p][i][j][0]*C[m-j][q]%Mod
							*f2[p][n-i][q]%Mod*g2[p][i][q])%Mod;
			}
	}
	printf("%lld\n",dp[k][n][m][1]);
	return 0;
}

Measured memory_bytes: 61440
#include <stdio.h>

int main(void) {
  int n, d[50], i, j, p=0;
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    scanf("%d", &d[i]);
  }
  for (i=0; i<(n-1); i++) {
    for(j=i+1; j<n; j++) {
      p += d[i]*d[j];
    }
  }
  printf("%d\n", p);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
  
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second
  
using namespace std;
  
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
 
int a[2][105];
int visit[2][105];
 
int main(){
    int n;
    while(cin >> n, n){
        memset( a, 0, sizeof(a) );
        memset( visit, 0, sizeof(visit) );
        rep(k, 2) rep(i, n) cin >> a[k][i];
        rep(k, 2) rep(i, 105) visit[k][i] = 0;
  
        priority_queue<pair<int, P>, vector<pair<int, P> >, greater<pair<int, P> > > q;
        q.push(MP(0, MP(0, 0)));
        q.push(MP(0, MP(1, 0)));
        int ans = -1;
        while(!q.empty()){
            P p = q.top().second;
            int d = q.top().first;
            q.pop();
 
            while(a[p.X][p.Y] == 1 && a[p.X][p.Y+1] == 1) p.Y++;
            if(visit[p.X][p.Y]) continue;
            visit[p.X][p.Y] = 1;
            if(p.Y >= n-1){
                ans = d;
                break;
            }
 
            rep(i, 3){
                int nx = !p.X;
                int ny = p.Y + i;
                if(ny >= n) ny = n-1;
		        while(a[nx][ny] == 2) ny--;
                q.push(MP(d+1, MP(nx, ny)));
            }
        }
        if(ans != -1) cout << ans << endl;
        else cout << "NA" << endl;
    }
 
    return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    int k, n;
    cin >> n >> k;
    vector<int> p(n);
    rep(i, n) cin >> p[i];
    map<int, double> m;
    ll e = 0;
    repr(i, 1, 1001){
        e += i;
        m[i] = (double)e / (double)i;
    }
    double sum = 0.0, ans = 0.0;
    rep(i, n){
        sum += m[p[i]];
        if (i+1 < k){
            continue;
        }
        ans = max(ans, sum);
        sum -= m[p[i-k+1]];
    }
    printf("%.7lf\n", ans);
    return 0;   
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int INF = 1000000007;

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

  int64_t N, K;
  cin >> N >> K;

  int64_t A[N], F[N];
  rep(i, N) cin >> A[i];
  sort(A, A+N);
  reverse(A, A+N);

  rep(i, N) cin >> F[i];
  sort(F, F+N);
  pair<int64_t, int64_t> P[N];
  rep(i, N){
    P[i].first = A[i]*F[i];
    P[i].second = F[i];
  }
  sort(P, P+N);

  int64_t left = -1, right = P[N-1].first, middle;
  while(right-left > 1){
    middle = (left+right)/2;
    int64_t sum = 0;
    for(int i=0;i<N;i++){
      sum += max((int64_t)0, (P[i].first + P[i].second - 1 - middle) / P[i].second);
    }
    if(sum > K) left = middle;
    else right = middle;
  }
  cout << right << endl;
}

Measured memory_bytes: 6528
A, B = map(int, input().split())

p_lst = []
f = False
for p in range(1, 100*11):
    if int(p*0.08) == A and int(p*0.1) == B:
        p_lst.append(p)
        f = True
if not f:
    print(-1)
else:
    print(min(p_lst))

Measured memory_bytes: 63700
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>

#define INF (1<<21)
#define swap(a,b) {a=a+b; b=a-b; a=a-b;}
#define abs(a) (a > 0 ? a:-a)
#define min(a,b) {a > b ? b:a}
#define max(a,b) {a > b ? a:b}
using namespace std;


#define MAX_W 1000
#define MAX_N 1000
#define MAX_VALUE 10000
#define MAX_WEIGHT 1000

int dp[MAX_W + 1];
void q42() {
	int W, N;
	int cnt = 1;
	for (; cin >> W;) {
		if (!W) break;

		cin >> N;
		vector<pair<int, int> > Item;
		for (int i = 0; i < N; i++) {
			int value, weight;
			char tmp;
			cin >> value >> tmp >> weight;
			Item.push_back(make_pair(value, weight));
		}

		for (int i = 0; i <= W; i++) {
			dp[i] = -1;
		}
		dp[0] = 0;

		for (int i = 0; i < N; i++) {
			int value = Item[i].first;
			int weight = Item[i].second;
			for (int j = W; j >= 0; j--) {
				if (j - weight < 0) continue;
				if (dp[j - weight] == -1) continue;
				dp[j] = max(dp[j], dp[j - weight] + value);
			}
		}

		int ans_value = 0, ans_weight = 0;
		for (int i = 0; i <= W; i++) {
			if (ans_value < dp[i]) {
				ans_value = dp[i];
				ans_weight = i;
			}
		}

		cout << "Case " << cnt++ << ":" <<"\n";
		cout << ans_value << "\n";
		cout << ans_weight << "\n";
	}
}

int main() {
	q42();
	return 0;
}

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

class Main{

	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		while(true){

			String str = br.readLine();

			if(str.equals("-")){
				break;
			}

			int num = Integer.parseInt(br.readLine());

			for(int i = 0; i < num; i++){
				int len = Integer.parseInt(br.readLine());
				String bottom = str.substring(0, len);
				String top = str.substring(len);
				str = top + bottom;
			}

			sb.append(str + "\n");

		}

		System.out.print(sb);

	}
}

Measured memory_bytes: 24292
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <cassert>

// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define MT make_tuple

using namespace std;

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

int s[20][20];
int visit[20][20];

vector<int> G[20];

int dx[] = {-1, -1, 0, 1, 1, 0};
int dy[] = {0, -1, -1, 0, 1, 1};

int n, c;
int check(){
    MEMSET(visit, 0);

    int res = 0;
    rep(i, n) rep(j, i+1){
        if(visit[i][j] || !s[i][j]) continue;
		visit[i][j] = 1;
        queue<P> q;
        q.push(MP(j, i));
        int x = s[i][j];
        bool ok = false;
        int cnt = 1;
        while(!q.empty()){
            P p = q.front();
            q.pop();

            rep(d, 6){
                int nx = p.first + dx[d], ny = p.second + dy[d];
                if(nx < 0 || ny < 0) continue;
                if(s[ny][nx] < 0) continue;
                if(s[ny][nx] != x) ok |= s[ny][nx] == 0;
                else{
                    if(visit[ny][nx]) continue;
                    visit[ny][nx] = 1;
                    ++cnt;
                    q.push(MP(nx, ny));
                }
            }
        }
		if (ok) continue;
        if(x == c) res -= cnt;
        else res += cnt;
    }
	return res;
}

int main(){
	ios::sync_with_stdio(false);

	while (cin >> n >> c, n){
        MEMSET(s, -1);
        rep(i, n) rep(j, i+1) cin >> s[i][j];
        int ans = -1000;
    	rep(i, n) rep(j, i+1) {
            if(s[i][j]) continue;
            s[i][j] = c;
            ans = max(ans, check());
            s[i][j] = 0;
        }
        cout << ans << endl;
    }

	return 0;
}

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

// 086 C
int main()
{
    int N;
    cin >> N;

    vector<vector<int>> vec(N+1);
    vec.at(0) = {0, 0, 0};
    for (int i = 1; i < N+1; i++)
    {
        vector<int> vec2(3);
        for (int j = 0; j < 3; j++)
            cin >> vec2.at(j);
        vec.at(i) = vec2;
    }

    bool p = true;
    for (int i = 0; i < N; i++)
    {
        int dt = vec.at(i+1).at(0) - vec.at(i).at(0);
        int dist = abs(vec.at(i+1).at(1) - vec.at(i).at(1)) + abs(vec.at(i+1).at(2) - vec.at(i).at(2));

        if (dt < dist) p = false;
        if (dt % 2 != dist % 2 ) p = false;
        
    }

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


Measured memory_bytes: 5760
n = gets.to_i
arr = gets.split.collect{|item| item.to_i}  #「配列の要素を置き換えるメソッド」a.collect{|item|...} または a.map{|item|...}
                                            # arr = gets.split.map(&:to_i) または　arr = gets.split.collect(&:to_i) も可能
sum = 0

arr.each do |i|
    sum += i
end

print arr.min, " ", arr.max, " ", sum, "\n"


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define hash dhsjakhd
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;

ll n,m,T,k,d;
const ll big = 1000000007;

vector<vi> C(200001, vi());
vector<vi> CW(200001, vi());

ll CS[200001] = {0};
ll PAR[200001] = {0};
ll TOT[200001] = {0};

ll MAP[200001] = {0};

void dfs1(ll i, ll par, ll ma, ll after, bool bad){
    CS[i]++;
    ma = max(ma,i);
    bool bad2 = bad;

    if(i != 0){
        if((i > MAP[ma] && i != ma) || (bad && i != ma)){
            CS[after]--;
            bad2 = 1;
        }
        else{
            CS[ma]--;
        }
    }
    if(i==ma)bad2 = 0;
    PAR[i] = par;
    for(int c1 = 0; c1 < sz(C[i]); c1++){
        ll a = C[i][c1];
        if(a != par){
            MAP[a] = ma;
            ll after2 = after;
            if(i >= ma){
                after2 = a;
            }
            dfs1(a,i,ma, after2, bad2);
        }
    }
}

void dfs2(ll i, ll par){
    for(int c1 = 0; c1 < sz(C[i]); c1++){
        ll a = C[i][c1];
        if(a != par){
            dfs2(a,i);
            CW[i][c1] = TOT[a]+CS[a];
            TOT[i] += TOT[a]+CS[a];
        }
    }
}

ll ANS[200001] = {0};

void dfs3(ll i, ll par, ll tail){
    ANS[i] = 1+TOT[i]+tail;
    ll tail2 = ANS[i];
    for(int c1 = 0; c1 < sz(C[i]); c1++){
        ll a = C[i][c1];
        if(a != par){
            tail2 -= CW[i][c1];
            dfs3(a,i,tail2);
            tail2 += CW[i][c1];
        }
    }

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,e;

    cin >> n;
    for(int c1 = 0; c1 < n-1; c1++){
        cin >> a >> b;
        a--;
        b--;
        C[a].push_back(b);
        C[b].push_back(a);
        CW[a].push_back(0);
        CW[b].push_back(0);
    }
    MAP[0] = -1;
    dfs1(0,-1,-1,0,0);
    dfs2(0,-1);
    dfs3(0,-1,0);
    for(int c1 = 1; c1 < n; c1++){
        cout << ANS[c1]-1 << " ";
    }

    return 0;
}


Measured memory_bytes: 46976
/*应该是线段树，好像见过，但是不大会做*/
/*记得补题：D，E*/

//题解： 双端队列，每反转奇数次，先尾部添加《=》向头部添加，代码不过三十行
//还是体现在思维上啊，就算不用双端队列，思维对的话也是做的出来的。
#include<bits/stdc++.h>
using namespace std;
char s[100005];
int main()
{
    cin>>s;
    deque<char> de;
    for(int i=0;i<strlen(s);i++)
        de.push_back(s[i]);
    int n;  cin>>n;
    int cnt=0,tmp;
    while(n--)
    {
        cin>>tmp;
        if(tmp==1){
            cnt++;
            continue;
        }
        else
        {
            int i;
            char ch;
            cin>>i>>ch;
            if(i==1){
                if(cnt&1)
                    de.push_back(ch);
                else
                    de.push_front(ch);    
            }
            else if(i==2){
                if(cnt&1)
                    de.push_front(ch);
                else 
                    de.push_back(ch);
            }
        }
    }
    
    if(cnt&1)
        {
            while(!de.empty()){
                cout<<de.back();
                de.pop_back();
            }
        }
        else
        {
            while(!de.empty()){
                cout<<de.front();
                de.pop_front();
            }
        }
    return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

int main(){
    ll n,a,b; cin >> n >> a >> b;
    if((b-a)%2 == 1) puts("Borys");
    else puts("Alice");
}


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

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  long long a, b; cin >> a >> b;
  if (abs(b - a)&1) cout << "IMPOSSIBLE\n";
  else cout << (a + b) / 2 << '\n';
}


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

int main()
{
    int a,b,c;
    
    cin >> a >> b >> c;
    
    if(a < b && b < c)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3108
N,M = map(int,input().split())
LRD = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for L,R,D in LRD:
    E[L-1][R-1] = D
    E[R-1][L-1] = -D

V = [None]*N
breakFlg = False
for i in range(N):
    if V[i]!=None:continue
    V[i] = 0
    q = [i]
    while q:
        j = q.pop()
        v = V[j]
        for k,d in E[j].items():
            if V[k] == None:
                V[k] = v+d
                q.append(k)
ans = True
for l,e in enumerate(E):
    for r,d in e.items():
        ans = ans and V[r]-V[l]==d
    if not ans:break
print("Yes" if ans else "No")

Measured memory_bytes: 131696
#include <iostream>
#include <string.h>
#include <algorithm> 
using namespace std;

int main(){
string s;
string t="keyence";
int n=0;
int h=0;
int l;
int x;
cin>>s;
 l=s.length();
if(n==0){
  if(s[h]!='k'){
     n=1;
    
       }
  else{
h++;
}
}
if(n==0){
  if(s[h]!='e'){
    n=1;
   }
  else{
h++;
}
}
if(n==0){
  if(s[h]!='y'){
    n=1;
   }
  else{
h++;
}
}
  
if(n==0){
  if(s[h]!='e'){
    n=1;
   }
  else{
h++;
}
} 

if(n==0){
  if(s[h]!='n'){
    n=1;
   }
  else{
h++;
}
}

if(n==0){
  if(s[h]!='c'){
    n=1;
   }
  else{
h++;
}
}  

if(n==0){
  if(s[h]!='e'){
    n=1;
   }
}

x=7-h; 
if(n==1){
if(h==0){ 
if(s[l-x]!='k'){
n=2;
}
else{
h++;
x--;
}
}
}
  
if(n==1){
if(h==1){ 
if(s[l-x]!='e'){
n=2;
}
else{
h++;
x--;
}
}
}
  
if(n==1){
if(h==2){ 
if(s[l-x]!='y'){
n=2;
}
else{
h++;
x--;
}
}
}
  
if(n==1){
if(h==3){ 
if(s[l-x]!='e'){
n=2;
}
else{
h++;
x--;
}
}
}  
  
if(n==1){
if(h==4){ 
if(s[l-x]!='n'){
n=2;
}
else{
h++;
x--;
}
}
}

if(n==1){
if(h==5){ 
if(s[l-x]!='c'){
n=2;
}
else{
h++;
x--;
}
}
}
  
if(n==1){
if(h==6){ 
if(s[l-x]!='e'){
n=2;
}
else{
h++;
x--;
}
}
}
  
if(n==2){
cout<<"NO";
}
else{
cout<<"YES";
}
  
}



Measured memory_bytes: 256
S=input()
n=len(S)
ans=0
for i in range(2**(n-1)):
  key=str(bin(i))[2:].zfill(n-1)
  f=S[0]
  for j in range(1,n):
    if key[j-1]=="0":
      f+=S[j]
    else:
      f+="+"+S[j]
  ans+=eval(f)
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
typedef long long ll;

int next_pos[maxn][26];
int map1[256], map2[256];

void init(){
    memset(map1, 0, sizeof(map1));
    memset(map2, 0, sizeof(map2));
    memset(next_pos, -1, sizeof(next_pos));
}

int main()
{
    string s,t;
    while(cin>>s>>t){
        init();
        for(int i=0;i<(int)s.length();i++){
            map1[s[i]]++;
        }
        for(int i=0;i<(int)t.length();i++){
            map2[t[i]]++;
        }
        bool flag = true;
        for(int i=0;i<(int)t.length();i++){
            if(map1[t[i]] == 0) {
                flag = false;
                break;
            }
        }
        if(!flag){
            cout<<-1<<endl;
        }
        else{
            int n = (int)s.length(), m = (int)t.length();
            s = s+s;
            for(int j=0;j<26;j++){
                next_pos[n*2][j] = 2*n;
            }
            for(int i=2*n - 1;i>=0;i--){
                for(int j=0;j<26;j++){
                    next_pos[i][j] = next_pos[i+1][j];
                }
                next_pos[i][s[i] - 'a'] = i+1;
            }
            ll ans = 0;
            for(int i=0;i<m;i++){
                int c = t[i] - 'a';
                int pos = ans % n;
//                cout<<next_pos[pos][c]<<" "<<pos<<endl;
                ans += next_pos[pos][c] - pos;
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;

#define rep(a,n) for(int a = 0;a < n;a++)
#define repi(a,b,n) for(int a = b;a < n;a++)

const ull mod = 1000000007;

int main(void)
{
	ll n;
	cin >> n;
	vector<ll> vs(n);
	rep(i, n)
	{
		cin >> vs[i];
		vs[i] *= -1;
	}
	vector<ll> s;
	ll color = 0;
	rep(i, n) {
		auto item = vs[i];
		auto u = upper_bound(s.begin(), s.end(), item);
		if (u == s.end()) {
			color++;		
			s.push_back(item);
		}
		else {
			*u = item;
		}
	}
	cout << color << endl;
	return 0;
}


Measured memory_bytes: 2168
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
int const INF=1001001001;
ll const LINF=1001001001001001001;
ll const MOD=1000000007;

ll H,W,M;
ll h[300000];
ll w[300000];

int main(){
    cin>>H>>W>>M;
    rep(i,M) cin>>h[i]>>w[i];

    vector<ll> cnth(H),cntw(W);
    rep(i,M){
        cnth[h[i]-1]++;
        cntw[w[i]-1]++;
    }

    ll suph=0,supw=0;
    vector<ll> idxh,idxw;
    rep(i,H){
        if(cnth[i]>suph){
            suph=cnth[i];
            idxh.clear();
            idxh.push_back(i);
        }else if(cnth[i]==suph){
            idxh.push_back(i);
        }
    }
    rep(i,W){
        if(cntw[i]>supw){
            supw=cntw[i];
            idxw.clear();
            idxw.push_back(i);
        }else if(cntw[i]==supw){
            idxw.push_back(i);
        }
    }

    map<P,ll> m;
    rep(i,M) m[P(h[i]-1,w[i]-1)]++;

    ll ans=suph+supw-1;
    rep(i,idxh.size()){
        rep(j,idxw.size()){
            if(m[P(idxh[i],idxw[j])]==0){
                ans++;
                goto a;
            }
        }
    }
    a:;

    cout<<ans<<endl;
}

Measured memory_bytes: 35976
#include<stdio.h>

int main(){
	int s[10000], t[500];
	int i,j,n,q,ans=0;	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",&s[i]);

	scanf("%d",&q);
	for(i=0;i<q;i++)scanf("%d",&t[i]);

	for(i=0;i<q;i++){
		for(j=0;j<n;j++){
			if(t[i]==s[j]){
				ans++;
				break;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}



Measured memory_bytes: 2732
#include <iostream>
using namespace std;
 
int main(){
  int N , A;
  cin >> N >> A;
  if (N % 500 == 0){
    cout << "Yes" << endl;
  }else{
    if ((N % 500) <= A){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int stack[101] = {0};
  int ans[101] = {0};
  int n;
  int i = 0, j = 0;

  while (scanf("%d", &n) != EOF) {

    if (n == 0){
      i--;
      ans[j] = stack[i];
      j++;
    }

    else {
      stack[i] = n;
      i++;
    }
  }

  for (i = 0; i < j; i++)
    printf("%d\n", ans[i]);

  return 0;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD


ll K;
char S[1010];
ll mk[1010];
ll i, j, k,ans;



int main(){
    scanf("%s%lld", S, &K);
    ll Sn = strlen(S);
    for (j = 1; S[j];j++){
        if(S[j]!=S[j-1]){
            break;
        }
    }
    if (j==Sn)
    {
        printf("%lld", j*K / 2);
        return 0;
    }
    for (i = 0; i < Sn;i++){
        S[Sn + i] = S[i];
    }
    
    k = j;
    for (i = j; i <= Sn+j; i++)
    {
        if(S[i-1]!=S[i]){
            //printf("%lld:%lld,%lld ", i,k,ans);
            ans += (i - k) / 2*K;
            if(k<Sn&&Sn<=i){
                ans -= (i - k) / 2;
                ans += (Sn - k) / 2;
                ans += (i-Sn) / 2;
            }
            k = i;
        }
    }
    printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 384
#define  _USE_MATH_DEFINES

#define  rep(i, n) for(int i = 0; i < n; i++)
#define  repx(i, a, n) for(int i = a; i < n; i++)
#define  loop while(1)
#define  lli long long int
#define  aryout(ary) rep(i, ary.size()) cout << ary[i] << (i < ary.size() - 1 ? " " : "\n");
#define  arysort(v) sort(v.begin(), v.end())
#define  aryreverse(v) reverse(v.begin(),v.end())
#define  arysum(v) accumulate(v.begin(), v.end(), 0)
 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <utility>
#include <set>

using namespace std;

int main() {

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

  lli ans = 0;

  int max_nCr = n / 2 + 2;
  vector<vector<lli>> nCr(max_nCr, vector<lli>(max_nCr, 0));

  nCr[0][0] = 1;
  rep(i, max_nCr) rep(j, i+1)
    nCr[i][j] = (j == 0 ? 1 : nCr[i-1][j-1] + nCr[i-1][j]);

  int max_bk = (n % 2 == 0 ? n / 2 : n / 2 + 1);
  int max_wh = (n % 2 == 0 ? n / 2 - 1 : n / 2);

  repx(bk, 1, max_bk+1) {

    //cout << "bk: " << bk << " ";
    int wh = bk - 1;
    //cout << "wh: " << wh << " ";
    int left = (n -(bk + wh)) / (k - 1);

    int selection = min(bk, left);
    //cout << "selection: " << selection << " ";
    rep(thick, selection+1) {
      //cout << "thick: " << thick << " ";
      ans += nCr[bk][thick];
      //cout << "nCr: " << nCr[bk][thick] << " ";
    }
    //cout << "ans: " << ans << endl;
  }

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3168
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, s: "List[str]"):
    l = [''.join(sorted(list(i))) for i in s]
    from collections import Counter
    c = Counter(l)

    import math
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    ans = 0
    for k, v in c.most_common():
        if v >= 2:
            ans += combination(v, 2)

    print(ans)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, s)

if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define smaller_queue  priority_queue <ll, vector<ll>, greater<ll> >
//------------------------------------------------------

ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

int main() {
    ll n, k;
    cin >> n >> k;

    cout << CEIL(n - 1, k - 1) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <stack>
#include <vector>
using namespace std;

vector <int> graph[100005];
int distance[100005];
bool visited[100005];
int paths[100005];

void dfs (int a) {
    if (!visited[a]){
        visited[a] = true;
        for (int b : graph[a]){
            int pom = max(::distance[b], ::distance[a] + 1);
            ::distance[b] = pom;
            paths[b]--;
            if (paths[b] == 0)
            dfs(b);
        }
    }
}



int main()
{
    int N, K, a, b;
    cin >> N >> K;
    for (int i = 0; i < K; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        paths[b]++;
    }
    
    for (int i = 1; i < N + 1; i++){
        if (!visited[i] && paths[i] == 0)
            dfs(i);
    }
    int ans = 0;
    for (int i = 1; i < N + 1; i++){
        ans = max(ans, ::distance[i]);
    }    
    cout << ans;
}

Measured memory_bytes: 9728
import sys

input = sys.stdin.readline

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for f in range(N-2):
	fl = L[f]
	s = f+1
	t = f+2
	while s<=N-2:
		sl = L[s]
		# print(f,s)
		if t<=N-1:
			while fl+sl>L[t]:
				t += 1
				if t==N: break
		ans += t-(s+1)
		# print(f,s,t,'',(t-(s+1)))
		s += 1

print(ans)

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

int main(){
	int h,w,n;
	cin >> h >> w >> n;
	int g = max(h,w);
	
	int temp = 0;
	int ans = 0;
	while(temp < n){
		temp += g;
		ans++;
	}
	
	cout << ans << endl;
	
}



Measured memory_bytes: 256