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

#define int long long

signed main(){
    int n, m;
    cin >> n >> m;
    int g = __gcd(n, m);
    int l = n/g*m;
    string s, t;
    cin >> s >> t;

    int a = 0;
    int b = 0;
    map<int, int> mp;
    for(int i = 0;i < n;i++){
        mp[i*(l/n)] = s[i];
    }

    for(int i = 0;i < m;i++){
        int tmp = mp[i*(l/m)];
        if(tmp != t[i] && tmp != 0){
            cout << -1 << endl;
            return 0;
        }
    }

    cout << l << endl;
    return 0;
}






Measured memory_bytes: 10880
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define print(v) cout<<v<<endl;
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;

vector<ll> vec(100005,INF);
vector<vector<P>> G(100005, vector<P>(0));

bool dfs(ll x, ll &Max, ll &Min){
    if(vec[x]==INF)vec[x]=0;
    bool ret=1;
    for(auto p: G[x]){
        //相手が探索済みで、矛盾が生じたとき
        if(vec[p.first]!=INF&&vec[p.first]-vec[x]!=p.second)ret=0;
        //未探索なら探索
        else if(vec[p.first]==INF){
            vec[p.first]=vec[x]+p.second;
            chmax(Max,vec[p.first]);
            chmin(Min,vec[p.first]);
            if(!dfs(p.first,Max,Min))ret=0;
        }
    }
    return ret;
}

int main(){
    ll N;
    cin >> N;
    ll M;
    cin >> M;
    vector<ll> L(M,0);
    vector<ll> R(M,0);
    vector<ll> D(M,0);
    for(ll i=0;i<M;i++)cin>>L[i]>>R[i]>>D[i];
    for(ll i=0;i<M;i++){
        G[L[i]].emplace_back(P(R[i],D[i]));
        G[R[i]].emplace_back(P(L[i],-D[i]));
    }
    for(ll i=1;i<=N;i++){
        ll Min=0,Max=0;
        if(vec[i]==INF&&!dfs(i,Max,Min)){
            print("No")
            return 0;
        }
        if(Max-Min>1000000000){
            print("No")
            return 0;
        }
    }
    print("Yes")
    return 0;
}


Measured memory_bytes: 23040
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        List<PriorityQueue<Integer>> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            PriorityQueue<Integer> set = new PriorityQueue<>();
            list.add(set);
        }

        for(int i = 0; i < n; i++) {
            int u = sc.nextInt() - 1;
            int k = sc.nextInt();
            for(int j = 0; j < k; j++) {
                list.get(u).add(sc.nextInt() - 1);
            }
        }

        int[] dist = new int[n];
        for(int i = 0; i < n; i++) {
            dist[i] = -1;
        }

        Queue<Integer> task = new ArrayDeque<>();
        task.add(0);
        dist[0] = 0;
        while(!task.isEmpty()) {
            int i = task.poll();
            while(!list.get(i).isEmpty()) {
                int j = list.get(i).poll();
                if(dist[j] < 0) {
                    dist[j] = dist[i] + 1;
                    task.add(j);
                }
            }
        }

        for(int i = 0; i < n; i++) {
            System.out.printf("%d %d\n", i + 1, dist[i]);
        }

        sc.close();
    }
}



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

int main() {
  string s;
  cin >> s;
  bool b = 0;
  for(int i = 1; i < s.size(); i++){
    if(s.at(i-1) == 'A' && s.at(i) == 'C'){
      b = 1;
      break;
    }
  }
  if(b)
    cout << "Yes"  << endl;
  else
    cout << "No" << endl;
      
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;
int main(){
	fastio;
	
	ll a,b;
	cin>>a>>b;
	if(a+b==3) cout<<"3\n";
	else if(a+b==4) cout<<"2\n";
	else if(a+b==5) cout<<"1\n";
	
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;

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

int main() {

    ll N,H;
    cin >> N >> H;
    ll a[N];
    ll b[N];
    ll aMax = 0;
    rep(i,N){
        cin >> a[i] >> b[i];
        aMax = max(aMax,a[i]);
    }
    sort(b,b+N);
    ll out = 0;
    ll sum = 0;
    rep(i,N){
        if(b[N-1-i]>aMax){
            sum += b[N-1-i];
            out++;
            if(sum>=H) break;
        }else break;
    }
    while(sum<H){
        sum += aMax;
        out++;
    }
    cout << out << endl;
    return 0;
}


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

int main() {
  
int S;
  cin>>S;
int  Sf=S/100;
int  Sb=S%100;
  if(Sf>12){
    if(Sb>12){
    cout<<"NA"<<endl;
    }
    else if(Sb==0){
    cout<<"NA"<<endl;
    }
	else if(Sb<=12){
    cout<<"YYMM"<<endl;
	}
    }
  else if(Sf==0){
    if(Sb>12){
    cout<<"NA"<<endl;
    }
    else if(Sb==0){
    cout<<"NA"<<endl;
    }
	else if(Sb<=12){
    cout<<"YYMM"<<endl;
	}
  }
    else if(Sf<=12){
    if(Sb>12){
    cout<<"MMYY"<<endl;
    }
    else if(Sb==0){
    cout<<"MMYY"<<endl;
    }
	else if(Sb<=12){
    cout<<"AMBIGUOUS"<<endl;
	  
    }


  }
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>

using namespace std;

namespace {

struct Proc {
  char name[12];
  int time;
};

class Queue {
 public:
  explicit Queue(size_t size)
      : size_(size), buf_(new Proc[size + 1]), head_(0), tail_(0) {}

  void Enqueue(Proc& p) {
    assert(!IsFull());
    buf_[tail_] = p;
    tail_ = next(tail_);
  }

  Proc& Dequeue() {
    assert(!empty());
    Proc& p = buf_[head_];
    head_ = next(head_);
    return p;
  }

  bool empty() const { return head_ == tail_; }

  bool IsFull() const {
    return (head_ == 0 && tail_ == size_) || head_ == tail_ + 1;
  }

 private:
  size_t next(size_t p) const { return p == size_ ? 0 : p + 1; }

  size_t size_;
  unique_ptr<Proc[]> buf_;
  size_t head_;
  size_t tail_;
};

}  // namespace

int main() {
  int n, quantum;
  cin >> n >> quantum;
  Queue q(static_cast<int>(n));
  for (int i = 0; i < n; ++i) {
    Proc p;
    scanf("%s %d", p.name, &p.time);
    q.Enqueue(p);
  }

  int current = 0;
  while (!q.empty()) {
    auto& p = q.Dequeue();
    const int used = min(p.time, quantum);
    p.time -= used;
    current += used;

    if (!p.time) {
      printf("%s %d\n", p.name, current);
      continue;
    }
    q.Enqueue(p);
  }
  return 0;
}

Measured memory_bytes: 3676
"""
問題の理解が困難
ノードi,jを結ぶ辺があるとき、ノードiは集合aに、ノードjは集合k+1（あるいは逆）に含まれるようにノードを集合に分ける。
その条件を満たす最大の集合の数を求める

1->2
2->3
2->4
みたいなのがあるときに、
・1と2は別の集合（1を集合１、２を集合とする）
・２と３は別の集合（２が集合２なので、３は集合１か３。できるだけ集合の数を多くとりたいので、３とする）
・２と４は別の集合（２が集合２なので、４は集合１か３。上に同じく３とする）
みたいな感じか。
なので、
あるノードから等距離にあるノードを同じ集合にする
という戦略をとれば、集合の数を最大化できる。
で、同じ集合に属するやつらの間に辺がある場合、辺を挟んだノードは別の集合にならなければならないので矛盾するからNG

↑から、木の直径＋１が最大の集合数になるので、double sweepだったか？何かでもとめればよいか？
"""



import heapq
from collections import deque



N = int(input())
S = [input() for _ in range(N)]
es = [[] for _ in range(N)]

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()

ans = 0
for i in range(N):
    q = deque()
    q.append(i)
    dist = [0] * N
    # 距離＋１が答えなので、起点を１としておく
    dist[i] = 1
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[nxt] == 0:
                dist[nxt] = dist[curr] + 1
                q.append(nxt)
 
    ans = max(ans, max(dist))

print(ans)

Measured memory_bytes: 42220
import sys
from itertools import accumulate
N = int(input())
A = [int(sys.stdin.readline()) for _ in range(N)]

Ar = [-1] + list(accumulate(A, max)) + [-1]
Al = [-1] + list(accumulate(A[::-1], max))[::-1] +[-1]
Ans = [None]*(N+1)
for i in range(1, N+1):
    Ans[i] = max(Ar[i-1], Al[i+1])
print('\n'.join(map(str, Ans[1:])))


Measured memory_bytes: 29932
n=int(input())
mod=1000000007
import math
ab=[]
n0=0
for i in range(n):
    a,b = map(int,input().split())
    if a==0 and b==0:
        n0+=1
        continue
    if b==0:
        ab.append( (1,0) )
    elif a==0:
        ab.append( (0,1) )
    else:
        gc = math.gcd(a,b)*b//abs(b)
        ab.append( (a//gc,b//gc) )
n_eff = n-n0

from collections import Counter
c=Counter(ab)

pairs =[]
for cc in c:
    n_dual = c[(-cc[1],cc[0])]
    if n_dual>0:
#         print(cc)
        pairs.append( (c[cc],n_dual) )

ans=1
for p in pairs:
    ans = ans*(pow(2,p[0],mod)+pow(2,p[1],mod)-1 ) %mod

amari = n_eff - sum(sum(p) for p in pairs)

ans=ans * pow(2,amari,mod) %mod 

ans=ans+n0-1
print(ans%mod)

Measured memory_bytes: 138884
#include <bits/stdc++.h>
using namespace std;
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 (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=6105,INF=1<<30;

struct UF{
    int n;
    vector<int> par,size,edge;
    
    void init(int n_){
        n=n_;
        par.assign(n,-1);
        size.assign(n,1);
        edge.assign(n,0);
        
        for(int i=0;i<n;i++){
            par[i]=i;
        }
    }
    
    int root(int a){
        if(par[a]==a) return a;
        else return par[a]=root(par[a]);
    }
    
    void unite(int a,int b){
        if(root(a)!=root(b)){
            size[root(a)]+=size[root(b)];
            edge[root(a)]|=edge[root(b)];
            par[root(b)]=root(a);
        }
    }
    
    bool check(int a,int b){
        return root(a)==root(b);
    }
};

int H,W;

bool check(int h,int w){
    if(h==0||h==H-1) return 1;
    if(w==0||w==W-1) return 1;
    return 0;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N>>H>>W;
    vector<vector<int>> hid(H),wid(W);
    UF uf;
    uf.init(N);
    for(int i=0;i<N;i++){
        int h,w;cin>>h>>w;
        h--;w--;
        hid[h].push_back(i);
        wid[w].push_back(i);
        
        if(check(h,w)) uf.edge[i]=1;
    }
    
    for(int i=0;i<H;i++){
        for(int j=0;j+1<si(hid[i]);j++){
            uf.unite(hid[i][j],hid[i][j+1]);
        }
    }
    
    for(int j=0;j<W;j++){
        for(int i=0;i+1<si(wid[j]);i++){
            uf.unite(wid[j][i],wid[j][i+1]);
        }
    }
    
    set<int> SE;
    for(int i=0;i<N;i++){
        SE.insert(uf.root(i));
    }
    
    int ans=0,cnt=0;
    
    for(int a:SE){
        ans+=uf.size[a]-1;
        if(uf.edge[a]) cnt++;
    }
    
    if(si(SE)==1) ans+=0;
    else if(cnt==0){
        ans+=si(SE)+si(SE)-1;
    }else{
        ans+=si(SE)-1+si(SE)-1;
    }
    
    cout<<ans<<endl;
}




Measured memory_bytes: 11340
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=1000000000;
const ll LINF=4000000000000000010;
int main(){
    int n,k;cin>>n>>k;
    int t[100010];
    int ans=n;
    for(int i=0;i<n;i++){
        cin>>t[i];
    }
    vector<int> v;
    for(int i=1;i<n;i++){
        v.push_back(t[i]-t[i-1]-1);
    }
    sort(all(v));
    for(int i=0;i<n-k;i++){
        ans+=v[i];
    }
    cout<<ans<<endl;
}	



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

constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
using namespace std;
using ll = long long int;
using ull =  unsigned long long int;

int main() {
	int N, X;
	cin >> N >> X;
	vector<int> L(N);
	for (int i = 0; i < N; i++)cin >> L[i];
	int pos = 0, ans = 0;
	for (int i = 0; i < N; i++) {
		if (pos <= X)ans++;
		pos += L[i];
	}
	if (pos <= X)ans++;
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  double N,T,A;
  cin >>N>>T>>A;
  vector <double> H(N);
  vector <double> t(N);
  
  for(int i=0;i<N;i++){
    cin >>H.at(i);
    t.at(i)=T-H.at(i)*0.006-A;
    if(t.at(i)<0){
      t.at(i)*=-1;
    }
  }
  int b=0;
  for(int i=0;i<N;i++){
    if(t.at(b)>t.at(i)){
      b=i;
    }
  }
  cout<<b+1<<endl;
    
}
  

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

using namespace std;

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

struct edge {
  ll to, cost;
  edge(ll to, ll cost):to(to), cost(cost){}
};

vector< vector<edge> > G;

P dfs(ll v, ll p)
{
  P ret = P(0, v);
  for(edge e : G[v]) {
    if(e.to == p) continue;
    if(G[e.to].size() == 1) continue;
    P dist = dfs(e.to, v);
    dist.first += e.cost;
    ret = max(ret, dist);
  }
  return ret;
}

ll diameter()
{
  P p = dfs(0, -1);
  P q = dfs(p.second, -1);
  return q.first;
}

int main()
{
  int n;
  while(cin >> n, n) {
    ll p[810], d[810];
    for(int i = 1; i < n; i++) cin >> p[i], p[i]--;
    for(int i = 1; i < n; i++) cin >> d[i];
    ll nodecost = 0LL;
    G.clear(); G.resize(n);
    for(int i = 1; i < n; i++) {
      G[p[i]].push_back(edge(i, d[i]));
      G[i].push_back(edge(p[i], d[i]));
      nodecost += d[i];
    }
    ll leafcost = 0LL;
    for(int i = 0; i < n; i++) {
      if(G[i].size() == 1) leafcost += G[i][0].cost;
    }
    ll diacost = diameter();
    cout << (nodecost - leafcost) * 3 - diacost + leafcost << endl;
  }
  
  return 0;
}

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

using namespace std;

const int mod = 1e9 + 7;

long long rec(int left, int right, vector<vector<long long>>& dp, vector<pair<int, int>>& infant){
  if(left > right) return 0;
  if(dp[left][right] != -1) return dp[left][right];
  
  long long l = rec(left + 1, right, dp, infant);
  long long r = rec(left, right - 1, dp, infant);
  
  l += (long long)infant[right - left].first * abs(infant[right - left].second - left);
  r += (long long)infant[right - left].first * abs(infant[right - left].second - right);
  
  if(l < r){
    dp[left][right] = r;
  }else{
    dp[left][right] = l;
  }
  
  return dp[left][right];
}

int main(){
  int N;
  cin >> N;
  
  vector<vector<long long>> dp(N, vector<long long>(N, -1));
  vector<pair<int, int>> infant(N);
  long long joy = 0;
  for(int i = 0; i < N; i++){
    int A;
    cin >> A;
    infant[i] = make_pair(A, i);
  }
  
  sort(infant.begin(), infant.end());
  
  cout << rec(0, N - 1, dp, infant) << endl;
  
  return 0;
}



Measured memory_bytes: 35112
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0]);
  var A = parseInt(input[1]);
  var B = parseInt(input[2]);
  var C = parseInt(input[3]);
  var D = parseInt(input[4]);
  var E = parseInt(input[5]);

  var AtCoder = function(N,A,B,C,D,E){
    this.move = [A,B,C,D,E];
    this.memNum = N;
  };

  AtCoder.prototype = {
    procedure: function(){
      return Math.ceil(this.memNum/Math.min(...this.move))+4;
    }
  }
  var atcoder = new AtCoder(N,A,B,C,D,E);
  console.log(atcoder.procedure());
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

#define int long long
#define f first

#define s second
using namespace std;

template<typename T> using vc = vector<T>;
using pii=pair<int, int>;

void xmax(int & a, int b){
    a=max(a, b);
}
void xmin(int& a, int b){
    a=min(a, b);
}

void print(vc <int> & a, string s){
    cerr << s << " : ";
    for (int i=0; i<a.size(); i++){
        cerr <<a[i] << " ";
    }
    cerr << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL_RUN
    freopen("input.txt", "r", stdin);
    int ttt;
    cin >> ttt;
    while(ttt--){
    #endif // LOCAL_RUN

    int n;
    cin >> n;
    vc <int> a (n);
    for (int i=0; i<n; i++){
        cin >> a[i];
    }
    int mini = 1e9;
    for (int i =0; i<=100; i++){
        int sum = 0;
        for (int j=0; j<n; j++){
            sum+=(a[j]-i)*(a[j]-i);
        }
        xmin(mini, sum);
    }
    cout << mini << "\n";


    #ifdef LOCAL_RUN
    }
    #endif // LOCAL_RUN
}


Measured memory_bytes: 256
def answer():
    point={}
    number=[]
    number_n=[]
    while 1:
        N=list(map(int,input().split(",")))
        if N==[0,0]:break
        number.append(N)
        number_n.append(N[1])
    number_n=sorted(number_n)[::-1]
    count=1
    co=number_n[0]
    for i in number_n:
        if i in point:continue
        elif i<co:
            count +=1
            co=i
            point[co]=count
        else:point[i]=count
    data={}
    for j in number:
        if j[1] in point:data[j[0]]=point[j[1]]
    return data

ans=answer()
while 1:
    try:print(ans[int(input())])
    except:break


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(cnt,e) for(ll cnt=0;cnt<e;cnt++ )
typedef pair<ll,ll> P;
const ll mod = 1e9+7;
const ll INF = INT64_MAX;
typedef tuple<ll,ll,ll,ll> T;

ll i,j,k;


int main(){
   ll N,M,C;
   cin>>N>>M>>C;
   V B(M);
   rep(i,M)cin>>B[i];
   vector<V> A(N,V(M));
   rep(i,N)rep(j,M)cin>>A[i][j];
   ll ans=0;
   rep(i,N){
       ll point=C;
       rep(j,M)point+=A[i][j]*B[j];
       if(point>0)ans++;

   }
   cout<<ans<<endl;
}


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

void int_display(int *A,int n)
{
  int i;
  for(i=0;i<n;i++){
    printf("%d",A[i]);
    if(i<n-1) printf(" ");
  }
  printf("\n");
}

void insertion_sort(int *A,int n)
{
  int i,j,key;
  int_display(A,n);
  for(i=1;i<=n-1;i++){
    key=A[i];
    j=i-1;
    while(j>=0 && A[j]>key){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=key;
    int_display(A,n);
  }
}

int main()
{
  int *A;
  int i,n;
  scanf("%d",&n);
  A=malloc(n*sizeof(int));
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  insertion_sort(A,n);
  return 0;
}

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

typedef long long int ll;
typedef vector<int> vi;			typedef vector<ll> vl;
typedef vector<vi> vvi; 		typedef vector<vl> vvl;
typedef pair<int, int> 	pii;	typedef pair<ll, ll> pll;
typedef vector<pii> vii; 		typedef vector<pll> vll;
typedef map<int,int> mii;
typedef vector<char> vc;
typedef vector<bool> vb;
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define rforne(i,n) for(int i=n;i>=1;i--)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define in insert
#define mp make_pair
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define min3(a, b, c) min(min(a, b), c)
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
const ll INFL = 1e18;
const int INFI = 1e9;
#ifdef KARAN
	#include "../../trace.h"
#else
    #define trace(args...)
#endif

ll div_floor(const ll &a,const ll &b) { return a / b - (((a ^ b) < 0) and a % b);}
ll div_ceil(const ll &a,const ll &b) { return a / b + (((a ^ b) >= 0) and a % b);}
ll modpow(ll a, ll b, ll m = MOD){a %= m; ll res = 1; 
	while (b) {if (b & 1)res = (res * a) % m; a = (a * a) % m; b >>= 1;} return res;}
ll bpow(ll a, ll b){ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a, ll m = MOD) {return modpow(a, m - 2, m);}
void graph(vvi &adj, int m) {int x, y; forn(i, m){cin>>x>>y; adj[--x].pb(--y); adj[y].pb(x);}}

void solve(){
	ll n, m, k;
	cin>>n>>m>>k;
	vl a(n+1, 0); forne(i, n) cin>>a[i], a[i]+=a[i-1];
	vl b(m, 0); forn(i, m){	cin>>b[i]; if(i!=0) b[i]+=b[i-1]; }
	ll ans = 0;
	forn(i, n+1)
		if(a[i]<=k){
			ll l2 = upper_bound(b.begin(), b.end(), k - a[i]) - b.begin();
			ans = max(ans, i + l2);
		}
	cout<<ans<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	#ifdef KARAN
		freopen("inp.txt", "r", stdin);
    	freopen("out.txt", "w", stdout);
    	freopen("err.txt", "w", stderr);
	#endif
	int t=1;
	while(t--)
		solve();
}

Measured memory_bytes: 6360
#include <bits/stdc++.h>
#if 1
#define int long long
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define stoi stoll
#else
#define MAX INT_MAX
#define MIN INT_MIN
#endif
#define INF MAX/2
#define ALL(obj) (obj).begin(), (obj).end()
#define fi first
#define se second
const int NIL = -1;
const int MOD = 1000000007;
#define REP(i,n) for (int i=0; i < (n); ++i)
#define FOR(i,a,b) for (int i=(a); i < (b); ++i)
using namespace std;

int pow(int x, int n) {int res=1; while(n){if(n&1)res*=x;x*=x;n>>=1;} return res;}
int get_gcd(int a, int b) {while(1){if (a < b) swap(a, b); if (b == 0) return a; a %= b;}}
int get_lcm(int a, int b) {return a * b / get_gcd(a, b);}
bool chmin(int &a, int b) {if(a>b){a=b; return true;} else return false;}
bool chmax(int &a, int b) {if(a<b){a=b; return true;} else return false;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//-------------------------テンプレここまで-------------------------//

signed main () {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  string s, t;
  cin >> s >> t;

  // dp[i][j] ... sのi文字目、tのj文字目(1-index)までのLCS長
  static int dp[3001][3001];
  // from[i][j] ... dp[i][j]の遷移元のインデックス
  static pair<int,int> from[3001][3001];
  REP (i, s.size()) {
    REP (j, t.size()) {
      if (s[i] == t[j]) {
        dp[i+1][j+1] = dp[i][j] + 1;
        from[i+1][j+1] = make_pair(i,j);
      }
      else if (dp[i+1][j] > dp[i][j+1]){
        dp[i+1][j+1] = dp[i+1][j];
        from[i+1][j+1] = make_pair(i+1,j);
      }
      else {
        dp[i+1][j+1] = dp[i][j+1];
        from[i+1][j+1] = make_pair(i,j+1);
      }
    }
  }

  // LCS長
  // cout << dp[s.size()][t.size()] << endl;

  // dpテーブルの可視化
  // cout << "  ";
  // REP(j, t.size()) cout << t[j] << " ";
  // cout << endl;
  // REP (i, s.size()) {
  //   cout << s[i] << " ";
  //   REP (j, t.size()) {
  //     cout << dp[i+1][j+1] << " ";
  //   }
  //   cout << endl;
  // }

  // LCSの復元
  // fromをたどってもとに戻っていく。
  // 遷移元がi-1,j-1のときもとの文字を記録する。
  string lcs;
  int i = s.size();
  int j = t.size();
  while (i != 0 && j != 0) {
    if(from[i][j].fi != i && from[i][j].se != j) lcs.push_back(s[i-1]);
    int ti = i; // iが書き換わるとjが正しく遷移できないのでiを記録しておく。
    i = from[i][j].fi;
    j = from[ti][j].se;
  }

  reverse(ALL(lcs));

  cout << lcs << endl;

  return 0;
}


Measured memory_bytes: 211328
#include<iostream>
#include<list>
#include<vector>
const int INF = 2001;
using namespace std;
list<int> L;
bool ok(int i) {
    for (list<int>::iterator it = L.begin(); it != L.end(); it++) if (i == *it) return 0;
    return 1;
}
int main() {
    L.push_back(0);
    int n; cin >> n;
    int M[100][100];
    int tmp = INF;
    int id = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> M[i][j];
            if (i == 0 && M[i][j] != -1) {
                if (M[i][j] < tmp) {
                    tmp = M[i][j];
                    id = j;
                }
            }
        }
    }
    L.push_back(id);
    int ans = tmp;
    tmp = INF;
    int OK[100];
    while (1) {
        tmp = INF;
        for (int i = 0; i < n; i++) OK[i] = ok(i); //reached?
        for (list<int>::iterator it = L.begin(); it != L.end(); it++ ) { //from reached
            for (int i = 0; i < n; i++) {
                if (M[*it][i] < tmp && M[*it][i] != -1 && OK[i]) {
                    tmp = M[*it][i];
                    id = i;
                }
            }
        }
        if (tmp == INF) break;
        ans += tmp;
        L.push_back(id);
    }
    cout << ans << endl;
    return 0;
    
}




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

int main() {

   vector<int> count(26,0);
   char x;

   while (scanf ("%c", &x) != EOF) {
     int n = x - 'A';
     if (n >= 0 && n< 26) {
       count.at(n)++;
     } else if (n >= 32 && n < 58) {
       count.at(n-32)++;
     }
   }

   for (int i=0; i<26; i++) {
     printf("%c : %d\n", i+32+'A', count.at(i));
   }

return 0;
}




Measured memory_bytes: 3216
W[2][100],c,q,h;main(n,i,j,l,f){for(;scanf("%d",&n)*n;printf(c?"%d\n":"NA\n",c-1)){int C[2][100]={0},Q[200]={h=q=0};for(i=2;i--;)for(j=0;j<n;)scanf("%d",W[i]+j++);**C=*C[1]=1;for(q=*Q=100;l=h/100,f=h%100,c=C[l][f];){if(W[l][f]==1)for(;f+1<n&&W[l][f+1]&1;)f++;for(;f&&W[l][f]>1;)f--;for(i=3;i--;)f+i<n&&!C[!l][f+i]?q=Q[q]=!l*100+f+i,C[!l][f+i]=c+1:0;h=Q[h];if(f==n-1||(c=0,!h))break;}}}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
using lint=long long;
using namespace std;

const int mod=1e9+7;

#include<map>
template<typename T> 
void factP(map<T,T> &m,T n)
{
	T x=n;
	for(T i=2;i*i<=n;i++)
	{
		while(x%i==0)
		{
			m[i]++;
			x/=i;
		}
	}
	if(x!=1)m[x]++;
	return;
}

int64_t pow(int64_t a,int64_t b,int64_t mod)
{
	if(b==0)return 1;
	if(b%2==0)
	{
		int64_t d=pow(a,b/2,mod);
		return (d*d)%mod;
	}else//if(b%2==1)
	{
		return (a*pow(a,b-1,mod))%mod;
	}
}

int64_t comb(int64_t n,int64_t r,int64_t p)
{
	int64_t ret=1;
	for(int64_t i=0;i<r;i++)
	{
		ret*=(n-i);
		ret%=p;
	}
	for(int64_t i=2;i<=r;i++)
	{
		ret*=pow(i,p-2,p);
		ret%=p;
	}
	return ret;
}

int main()
{
	int N,M;
	
	cin >> N >> M;
	
	map<int,int> m;
	factP(m,M);
	
	lint ans=1;
	for(auto&& i:m)
	{
		ans*=comb(i.second+N-1,i.second,mod);
		ans%=mod;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

#ifdef _DEBUG
#include "../../library/library/debug_template.cpp"
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

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

	int l = 0, r = N - 1;
	int ans = 0;
	while (l < r) {

		while (l < N && S[l] == 'R') l++;
		while (0 <= r && S[r] == 'W') r--;

		if (l < r) ans++;
		l++, r--;
	}

	cout << ans << "\n";

	return 0;
}



Measured memory_bytes: 3728
table = [[0, 1, 2, 3, 4, 5], [3, 1, 0, 5, 4, 2], [1, 5, 2, 3, 0, 4],
         [4, 0, 2, 3, 5, 1], [2, 1, 5, 0, 4, 3], [0, 2, 4, 1, 3, 5],
         [0, 3, 1, 4, 2, 5], [5, 1, 3, 2, 4, 0], [1, 2, 0, 5, 3, 4],
         [4, 3, 0, 5, 2, 1], [3, 0, 4, 1, 5, 2], [3, 5, 1, 4, 0, 2],
         [5, 4, 2, 3, 1, 0], [2, 5, 4, 1, 0, 3], [1, 3, 5, 0, 2, 4],
         [2, 0, 1, 4, 5, 3], [4, 2, 5, 0, 3, 1], [0, 4, 3, 2, 1, 5],
         [1, 0, 3, 2, 5, 4], [4, 5, 3, 2, 0, 1], [5, 3, 4, 1, 2, 0],
         [5, 2, 1, 4, 3, 0], [2, 4, 0, 5, 1, 3], [3, 4, 5, 0, 1, 2]]
color_table = %w(Red Yellow Blue Magenta Green Cyan).map
                .with_index {|c, i| [c, i]}.to_h

until (n = gets.to_i).zero?
  dices = n.times.map { gets.split.map {|c_name| color_table[c_name]} }
  pool = []
  count = 0
  
  dices.each do |color|
    check_f = true
    table.each do |t|
      next_dice = t.map {|idx| color[idx]}
      if pool.include?(next_dice)
        count += 1 if check_f
        check_f = false
      else
        pool << next_dice
      end
    end
  end
  
  puts count
end


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


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

    map<int, int> cnt;
    rep(i, n) {
        cnt[i] = 0;
    }
    rep(i, k) {
        int d; cin >> d;
        rep(j, d) {
            int a; cin >> a;
            a--;
            cnt[a]++;
        }
    }

    int ans = 0;
    for (auto e: cnt) {
        if (e.second == 0) {
            ans++;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3636
import * as fs from 'fs';
//in
// 2 900
//out
// Yes
function main(inp: string) {
    const [k, x] = inp.split(' ').map(Number);
    if (k*500>=x) {
        console.log('Yes');
    } else {
        console.log('No');
    }
}

main(fs.readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 7372
#include <iostream>
using namespace std;
int main(void){
    int N;
    cin >> N;
    int a[N+1];
    for(int i=1;i<=N;i++)cin >> a[i];
    int ans = 0;
    for(int i=1;i<=N;i+=2){
        if(a[i] % 2 == 1){
            ans++;
        }
    }
    cout << ans << endl;
    
}


Measured memory_bytes: 3156
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>

using namespace std;
using pii=pair<int,int>;
using ll=long long;

ll gcd(ll a, ll b)
{
    return (a%b==0)?b:gcd(b,a%b);
}

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

    ll a,b,c,d;
    cin>>a>>b>>c>>d;

    ll answer=b/c-a/c;
    if(a%c==0) answer+=1;
    answer+=b/d-a/d;
    if(a%d==0) answer+=1;
    ll e=c*d/gcd(c,d);
    answer-=b/e-a/e;
    if(a%e==0) answer-=1;

    cout<<b-a+1-answer;


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int m[10][10];
void small(int x,int y,int r) {
	if (y-r>=0) m[x][y-r]++;
	if (x-r>=0) m[x-r][y]++; 
	if (x+r<=9) m[x+r][y]++;
	if (y+r<=9) m[x][y+r]++;
	m[x][y]++;
}
void middle(int x,int y) {
	for (int i=-1; i<2; i++) for (int j=-1; j<2; j++) 
		if (x+i>=0 && x+i<=9 && y+j>=0 && y+j<=9) m[x+i][y+j]++;
}
void large(int x,int y) {
	middle(x,y);
	small(x,y,2);
    m[x][y]--;
}

int main() {
	int x,y,n,i,j,h,k;
	while(scanf("%d,%d,%d",&x,&y,&n)!=EOF) {
		if (n==1) small(x,y,1); 
		if (n==2) middle(x,y);
		if (n==3) large(x,y);
	}
    n=0; h=0; k=0;
	for (i=0;i<10;i++) for (j=0;j<10;j++) {
		if (m[i][j]==0) k++; else h=h<m[i][j] ? m[i][j] : h;
	}
    cout << k << endl << h << endl;
	return 0;
	}

Measured memory_bytes: 1208
#include<stdio.h>

int a[100000000];

int main(){
    int n;
    int i,tmp=0;
    scanf("%d",&n);

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

    for(i=n-1;i>=1;i--)
    printf("%d ",a[i]);
    printf("%d\n",a[0]);



    return 0;
}




Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
 
vector<string> dot_to_minenumber(const vector<string>& input_map);
 
int main(){
  //入力
  int H, W;
  cin >> H >> W;
  vector<string> input_map(H);
  for ( int i = 0; i < input_map.size() ; i++) cin >> input_map.at(i);
  
  //処理
  vector<string> output_map = dot_to_minenumber(input_map);
  
  //出力
  for ( string s : output_map ) cout << s << endl;
}
 
vector<string> dot_to_minenumber(const vector<string>& input_map){
  vector<string> ret_map = input_map;
  vector<int> row = { -1 , 0 , 1};
  vector<int> column = { -1 , 0 , 1};//ある点の周辺を調べる用
  for ( int i = 0 ; i < ret_map.size(); i++){
    for ( int j = 0 ; j < ret_map.at(0).size(); j++){//マップの全探索
      if ( ret_map.at(i).at(j) == '.'){//その点が地雷ではないとき
        int count = 0;
      	for ( int x : row ){
       	 for ( int y : column){
          	if (0 <= (i + x) && (i + x) < ret_map.size() && 
                0 <= (j + y) && (j + y ) < ret_map.at(0).size() &&
                ret_map.at(i + x).at(j + y) == '#' ) count++;//その点回りに文字が存在し、かつ地雷ならcount++
                   ret_map.at(i).at(j) = '0' + count;//(1)よく知らないけどこれでintをcharで代入できる
       	 }
      	}
        /*(1)の代わりにこれでも代入できる
        string s = to_string(count);
        ret_map.at(i).at(j) = s.at(0);
        */
      }//if文終了
    }
  }//ループ終了
  return ret_map;
}

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

int n,k;
char s[10010],ans[5010],res[5010];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline bool cmp()
{
	for (int i=1;i<=n;i++)
	{
		if (res[i]<ans[i]) return true;
		if (res[i]>ans[i]) return false;
	}
	return true;
}

int main()
{
	n=rd();k=rd();
	scanf("%s",s+1);
	int mn='z';
	for (int i=1;i<=n;i++) mn=min(mn,(int)s[i]);
	if (k>=15)
	{
		for (int i=1;i<=n;i++) putchar(mn);
		putchar('\n');
		return 0;
	}
	for (int i=1;i<=n;i++) s[n*2-i+1]=s[i];
	for (int i=1;i<=n;i++) ans[i]='z';
	if (k==1)
	{
		for (int i=n;i<=n*2;i++)
		{
			for (int j=1;j<=n;j++) res[j]=s[i-n+j];
			if (cmp()) for (int j=1;j<=n;j++) ans[j]=res[j];
		}
		for (int i=1;i<=n;i++) putchar(ans[i]);
		putchar('\n');
		return 0;
	}
	for (int i=n;i<=n*2;i++) if (s[i]==mn)
	{
		int cnt=0;
		for (int j=i;j;j--)
		{
			if (s[j]==mn) cnt++;
			else break;
		}
		if (cnt<<(k-1)>=n)
		{
			for (int j=1;j<=n;j++) putchar(mn);
			putchar('\n');
			return 0;
		}
		int now=cnt<<(k-1);
		for (int j=1;j<=now;j++) res[j]=mn;
		for (int j=now+1;j<=n;j++) res[j]=s[i-cnt-(j-now)+1];
		if (cmp()) for (int j=1;j<=n;j++) ans[j]=res[j];
	}
	for (int i=1;i<=n;i++) putchar(ans[i]);
	putchar('\n');
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
const long double EPS = 1e-14;
const int maxn = 100500;
const int mod = 1e9 + 7;


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector < int > a(n);
    for(auto &x : a) cin >> x;
    for(int i = 1 ; i < n ; ++i) a[i] += a[i - 1];
    int ans = 3e18;
    for(int mid = 1 ; mid < n - 1 ; ++mid){
        int smL = a[mid];
        int smR = a.back() - a[mid];
        int idxL = 0, idxR = n - 2;
        int lo = 0, hi = mid - 1;
        while(lo <= hi){
            int md = (lo + hi) >> 1;
            if(a[md] <= smL / 2) lo = md + 1;
            else hi = md - 1;
        }
        if(lo) idxL = lo - 1;
        lo = mid + 1, hi = n - 2;
        while(lo <= hi){
            int md = (lo + hi) >> 1;
            if(a[md] - a[mid] <= smR / 2) lo = md + 1;
            else hi = md - 1;
        }
        if(lo) idxR = lo - 1;
        for(int midL = max(0LL, idxL - 1) ; midL < min(mid, idxL + 2) ; ++midL)
            for(int midR = max(mid + 1, idxR - 1) ; midR < min(n - 1, idxR + 2); ++midR){
                vector < int > sms;
                sms.push_back(a[midL]);
                sms.push_back(a[mid] - a[midL]);
                sms.push_back(a[midR] - a[mid]);
                sms.push_back(a.back() - a[midR]);
                sort(all(sms));
                ans = min(ans, sms.back() - sms[0]);
            }
    }
    cout << ans << '\n';
    return 0;
}

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

int main() {
    int n, a;

    cin >> n >> a;

    int left = n - 500 * (n / 500) - a;
    if (left <= 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
using namespace std;

int main() {
	int dummy;
	int K, A, B;
	dummy = scanf("%d %d %d", &K, &A, &B);

	long long  count = K + 1;
	if (B - A > 2) {
		long long tatakeru = count - A;
		if (tatakeru % 2) tatakeru--;
		count = count - tatakeru + (long long)(B - A) * (tatakeru / 2);
	}

	printf("%lld\n", count);

	return 0;
}


Measured memory_bytes: 128
n,m = map(int, input().split())
num = list(map(int, input().split()))
num_new = sorted(num)
gap = []

for i in range(m-1):
	gap.append(num_new[i+1] - num_new[i])

gap_new = sorted(gap, reverse=True)
del gap_new[0:n-1]
count = 0

for i in gap_new:
	count += i

print(count)

Measured memory_bytes: 13968
#include <iostream>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

//Write your function here!



int main()
{
	int N;
	cin >> N;
	vector<int> seki(2);
	int ans = 0;
	for (int i = 0;i < N;i++) {
		cin >> seki.at(0);
		cin >> seki.at(1);
		ans = ans + (seki.at(1) - seki.at(0)) + 1;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N, M = map(int, input().split())
A = list(map(int, input().split()))
O = [list(map(int, input().split())) for _ in range(M)]

ope = UnionFind(N)

for i in range(M):
	ope.Unite(O[i][0], O[i][1])

cnt = 0

for i in range(N):
	if ope.isSameGroup(i+1, A[i]):
		cnt += 1

print(cnt)

Measured memory_bytes: 33152
#include<stdio.h>
#define NUM 100

int main(){

  int N,i,j,k,A[NUM],v;
  
  //入力
  scanf("%d",&N);
  
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  for(i=0;i<N;i++){
    printf("%d",A[i]);
    if(i!=N-1) printf(" ");
  }

  printf("\n");
  
  //処理と出力
  for(i=1;i<=N-1;i++){

    v=A[i];
    j=i-1;

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

    for(k=0;k<N;k++){
      printf("%d",A[k]);
      if(k!=N-1) printf(" ");
    }

    printf("\n");
    
  }

  return 0;
  
}



Measured memory_bytes: 2072
#include<iostream>
using namespace std;
int ans[31];
int main(void){
  ans[1] = 1; ans[2] = 2; ans[3] = 5; ans[4] = 8;
  for(int i = 5; i <= 30; ++i){
    if( i % 2 == 1 ){
      ans[i] = 2 * ans[i-1] + 1; 
    }else{
      ans[i] = ans[i-1] + ans[i-2] + 1;
    }
  }
  while(true){
    int n;
    cin>>n;
    if(cin.eof())
      break;
    cout << ans[n] << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

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

    rep(i,s.size()){
        s[i] += n;
        if((int)s[i] > 90)s[i] -= 26;
    }
    cout << s << endl;
    return 0;
}
 
 


Measured memory_bytes: 256
// スタックサイズ: 100MB

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }



int main() {

	ll H, W;
	cin >> H >> W;
	ll ma[10][10];
	rep(i, 10) rep(j, 10) cin >> ma[i][j];	

	ll d[10][10];
	rep(i, 10) rep(j, 10) d[i][j] = ma[i][j];
	rep(k, 10) rep(i, 10) rep(j, 10) {
		if (d[i][j] > d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j];
	}


	ll ans = 0;
	rep(i, H) rep(j, W) {
		ll A; cin >> A;
		if (A != -1) ans += d[A][1];
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 251;
#define fr(i,a,b) for(int i = a;i <= b; ++i)
#define nfr(i,a,b) for(int i = a;i >= b; --i)

int n,m;

inline int up(int x){
   return min((int)sqrt(4*n*n-x*x),2*n-1);
}

inline int down(int x){
   if(x >= n)return 0;
   return ceil(sqrt(n*n-x*x))-1;
}

int a[N],f[N][N];

inline void add(int &x,int y){
   x += y; if(x >= m)x -= m;
}

int main(){
   scanf("%d%d",&n,&m);
   
   int ans = 0;
   fr(i,0,n){
      int j = 2*n-1;
      memset(f,0,sizeof f);
      f[n][0] = 1;
      int cnt = 0;
      nfr(k,n-1,0){
         while(j >= n && up(j) <= down(k)){
            fr(l,0,i)f[k+1][l] = 1LL*f[k+1][l]*(1+up(j)-l-(2*n-1-j))%m;
            --j;
         }
         fr(l,0,i)add(f[k][l],1LL*f[k+1][l]*(1+up(k)-(2*n-1-(k-(i-l))))%m);
         fr(l,0,i-1)add(f[k][l+1],1LL*f[k+1][l]*(1+down(k)-l-(2*n-1-j))%m);
      }
      while(j >= n){
         f[0][i] = 1LL*f[0][i]*(1+up(j)-i-(2*n-1-j))%m;
         --j;
      }
      add(ans,(int)pow(-1,i)*f[0][i]);
      if(ans < 0)ans += m;
   }
   printf("%d\n",ans);
   return 0;
}


Measured memory_bytes: 512
N,K=gets.chomp.split(" ").map(&:to_i)
MOD=10**9+7
ret=0
(K..(N+1)).each do |k|
    min_sum = k*(k-1)/2
    max_sum = k*(N-k+N+1)/2
    ret += max_sum - min_sum + 1
    ret %= MOD
end
puts ret 


Measured memory_bytes: 14260
package main

import (
	"bufio"
		"os"
	"strings"
	"strconv"
		"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	for scanner.Scan() {
		input := strings.Split(scanner.Text(), " ")
		ele_t1 := [3]int{}
		ele_t2 := [3]int{}
		for i := range ele_t1 {
			ele_t1[i], _ = strconv.Atoi(input[i])
			ele_t2[i], _ = strconv.Atoi(input[i+3])
		}
		if ele_t1[0] < 0 || ele_t1[1] < 0 || ele_t1[2] < 0 ||
			ele_t2[0] < 0 || ele_t2[1] < 0 || ele_t2[2] < 0 {
				break
		}
		// t1 := time.Date(ele_t1[0], time.Month(ele_t1[1]), ele_t1[2], 0, 0, 0, 0, time.UTC)
		// t2 := time.Date(ele_t2[0], time.Month(ele_t2[1]), ele_t2[2], 0, 0, 0, 0, time.UTC)
		// diff := t2.Sub(t1)
		// fmt.Printf("%v\n", int64(diff/(time.Hour*24)))
		fmt.Println(ut2jd(ele_t2[0], ele_t2[1], ele_t2[2])-ut2jd(ele_t1[0], ele_t1[1], ele_t1[2]))
	}
}

func ut2jd(year, month, day int) int {
	if month <= 2 {
		year--
		month += 12
	}
	s := 3 + year/4 - year/100 + year/400
	s += 1720994 + year*365 + (month+1)*30 + (month+1)*3/5 + day
	return s
}



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

using namespace std;

#define debug(x) cout << #x << "::" << x << endl;
#define debug2(x, y) cout << #x << "::" << x << " " << #y << "::" << y << endl;
#define debug3(x, y, z) cout << #x << "::" << x << " " << #y << "::" << y <<" "<< #z << "::" << z << endl;

#define For(i, a, b) for (int i = a; i < b; i++)

typedef long long ll;
const ll mod = 1e9 + 7;
const int MAX = 5 * 1e3 + 5;
typedef pair<int, int> pii;

void add(ll &a, ll b)
{
    a = (a + b) % mod;
    if (a < 0) a += mod;
}

int main() {

    int n;
    cin>>n;

    vector<double> headProb(n+1);
    for(int i=1;i<=n;i++) cin>>headProb[i];

    vector<vector<double>> dp(n+1,vector<double>(n+1));

    dp[0][0] = 1;

    For(i,1,n+1) dp[i][0] = dp[i-1][0]*(1-headProb[i]);

    for(int i=1;i<=n;i++){
        for(int head=1;head<=i;head++){
            dp[i][head] = dp[i-1][head-1]*headProb[i] + dp[i-1][head]*(1-headProb[i]);
        }
    }

    double ans = 0;
    
    For(i,(n+1)/2,n+1){
        ans+=dp[n][i];
    }

    printf("%.10f\n",ans);
    return 0;

}

Measured memory_bytes: 70656
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=1;i<=n;i++)
#define REP(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
using namespace std;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
typedef pair<ll,ll> P;
int main(){
    int n; cin >> n;
    int ans;
    if(n%2==0) ans = n/2-1;
    else ans = (n-1)/2;
    cout << ans;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
#define lb lower_bound
#define ub upper_bound
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);ios::sync_with_stdio(false);



signed main(){
    ll x,a,b;cin>>x>>a>>b;
    ll n;cin>>n;
    rep(i,n){
        string s;cin>>s;
        if(s[0]=='n'){
            x+=a;
            x=max(x,0ll);
        }else if(s[0]=='t'){
            x+=b;
            x=max(x,0ll);
        }else{
            x=0;
        }
    }
    cout<<x<<endl;
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using ll = long long int;
 
int main(){
    int N;
    int X; 
    int Y;
    cin >> N;
    cin >> X;
    cin >> Y;
 
    vvi vec(N+1,vi(0));
    for(int i=2; i<N; i++){
        vec[i].push_back(i+1);
        vec[i+1].push_back(i);
    }
    vec[1].push_back(2);
    vec[X].push_back(Y);
    vec[Y].push_back(X);
    
    vector<ll> res(N,0);
    for(int i=1; i<N+1; i++){
      for(int j=i+1; j<N+1; j++){
              ll v = max(i, X) - min(i, X) + 1 + max(j, Y) - min(j, Y);
              ll w = j - i;
              ll x = min(v, w);
              res[x]++;
      }
    }

    for(int i=1; i<N; i++){
        cout << res[i] << endl;
    }
}

Measured memory_bytes: 384