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

#define pb push_back
#define ff first
#define ss second

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

const ll MAXN = 2 * 100 * 1000 + 17, mod = 1e9 + 7, inf = 2e15 + 17;

ll n, m, s, t, ds[MAXN], dt[MAXN], cnts[MAXN], cntt[MAXN], ans;
pair<pll, ll> edge[MAXN];
vector<pll> adj[MAXN];

void dijs() {
	fill(ds + 1, ds + n + 1, inf);
	set<pll> st;
	st.insert({0, s});
	ds[s] = 0;
	cnts[s] = 1;
	while (!st.empty()) {
		int u = st.begin() -> ss;
		st.erase(st.begin());
		for (auto i : adj[u]) {
			if (ds[i.ff] > ds[u] + i.ss) {
				st.erase({ds[i.ff], i.ff});
				ds[i.ff] = ds[u] + i.ss;
				cnts[i.ff] = 0;
				st.insert({ds[i.ff], i.ff});
			}
			if (ds[i.ff] == ds[u] + i.ss)
				(cnts[i.ff] += cnts[u]) %= mod;
		}

	}
}

void dijt() {
	fill(dt + 1, dt + n + 1, inf);
	set<pll> st;
	st.insert({0, t});
	dt[t] = 0;
	cntt[t] = 1;
	while (!st.empty()) {
		int u = st.begin() -> ss;
		st.erase(st.begin());
		for (auto i : adj[u]) {
			if (dt[i.ff] > dt[u] + i.ss) {
				st.erase({dt[i.ff], i.ff});
				dt[i.ff] = dt[u] + i.ss;
				cntt[i.ff] = 0;
				st.insert({dt[i.ff], i.ff});
			}
			if (dt[i.ff] == dt[u] + i.ss)
				(cntt[i.ff] += cntt[u]) %= mod;
		}

	}
}


int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	cin >> s >> t;
	for (int i = 1; i <= m; i++) {
		int v, u, w;
		cin >> v >> u >> w;
		adj[v].pb({u, w});
		adj[u].pb({v, w});
		edge[i] = {{u, v}, w};

	}
	dijs();
	dijt();
	if (cnts[t] == 0)
		return cout << 0 << endl, 0;
	ans = (cnts[t] * cntt[s]) % mod;
	for (int i = 1; i <= m; i++) {
		int x = edge[i].ff.ff, y = edge[i].ff.ss;
		if (ds[x] + dt[y] + edge[i].ss == ds[t] && abs(ds[x] - dt[y]) < edge[i].ss)
			(ans -= (((cnts[x] * cntt[y]) % mod) * ((cnts[x] * cntt[y]) % mod)) % mod) %= mod;
		if (ds[y] + dt[x] + edge[i].ss == ds[t] && abs(ds[y] - dt[x]) < edge[i].ss)
			(ans -= (((cnts[y] * cntt[x]) % mod) * ((cnts[y] * cntt[x]) % mod)) % mod) %= mod;
	}
	for (int i = 1; i <= n; i++)
		if (ds[i] + dt[i] == ds[t] && ds[i] == dt[i])
			(ans -= (((cnts[i] * cntt[i]) % mod) * ((cnts[i] * cntt[i]) % mod)) % mod) %= mod;
	ans += mod;
	ans %= mod;
	cout << ans << endl;
	return 0;
}


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

int main() {
  int x,y;
  cin>>x>>y;
  int ans=0;
  if(x==1&&y==1)ans+=400000;
  if(x==1)ans+=300000;
  if(x==2)ans+=200000;
  if(x==3)ans+=100000;
  if(y==1)ans+=300000;
  if(y==2)ans+=200000;
  if(y==3)ans+=100000;
  
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int s[1000000];
int main() {
    vector<int> V;
    int N,Q;
    scanf("%d %d",&N,&Q);
    for(int i=0;i<N;i++) {
        scanf("%d",&s[i]);
        V.push_back(s[i]);
    }
    sort(V.begin(),V.end());
    multiset<int> S;
    for(int i=0;i<Q;i++) {
        char type[7]; int x;
        scanf("%s %d",type,&x);
        if(type[0]=='A') {
            S.insert(s[x-1]);
        }else if(type[0]=='R') {
            S.erase(S.lower_bound(s[x-1]));
        }else {
            int l=0,r=1000000001;
            while(l!=r) {
                int m=(l+r)/2;
                int pos,prev=0,fail=0;
                for(multiset<int>::iterator itr=S.begin();itr!=S.end();itr++) {
                    pos=lower_bound(V.begin(),V.end(),*itr-m)-V.begin();
                    fail+=max(pos-prev,0);
                    prev=upper_bound(V.begin(),V.end(),*itr)-V.begin();
                }
                fail+=N-prev;
                if(fail<=x) r=m; else l=m+1;
            }
            if(l==1000000001) printf("NA\n");
            else printf("%d\n",l);
        }
    }
}

Measured memory_bytes: 8948
#!/usr/bin/perl

use strict;
use warnings;
use 5.010;

use Data::Dumper;

my @INPUT;
while (<>) {
    chomp;
    push @INPUT, $_;
}

my ($N, $K) = split " ", shift @INPUT;
my @h = @INPUT;

@h = sort {$a <=> $b} @h;

my $min = 1000000000000;
for (my $i = 0; $i + $K - 1 <= $#h; $i++) {
    my $diff = $h[$i + $K - 1] - $h[$i];
    if ($diff < $min) {
        $min = $diff;
    }
}
$min = $min * 1;
$min = "$min";
print "$min\n";

Measured memory_bytes: 22272
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s,c="CODEFESTIVAL2016";
  cin>>s;
  int i,j=0;
  for(i=0;i<s.size();i++){
    if(s.at(i)!=c.at(i))
      j++;
  }
  cout<<j<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double PI = 3.14159265358979;
const double E = 2.718281828459045;
const double root2 = sqrt(2);
typedef pair<int, int> P;
typedef unsigned int ui;
int main() {
	int w, h;
	while (cin >> w >> h,w) {
		int wall[100][100] = {};
		for (int i = 0; i <= 2 * w; i++) {
			wall[0][i] = 1;
			wall[2 * h][i] = 1;
		}
		for (int i = 0; i <= 2 * h; i++) {
			wall[i][0] = 1;
			wall[i][2 * w] = 1;
		}
		int c;
		for (int i = 1; i <= 2*h-1; i++){
			if (i % 2) {
				for (int j = 1; j <= w - 1; j++) {
					cin >> c;
					if (c)wall[i][2 * j] = 1;
				}
			}
			else {
				for (int j = 1; j <= w; j++) {
					cin >> c;
					if (c)wall[i][2 * j - 1] = 1;
				}
			}
		}
		vector<P> v; v.push_back({ 1,1});
		int d[100][100];
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				d[i][j] = (int)MOD;
			}
		}
		d[1][1] = 1;
		while (!v.empty()) {
			int len = v.size();
			for (int i = 0; i < len; i++) {
				int x = v[0].first; int y = v[0].second; v.erase(v.begin());
				if (wall[x + 1][y] == 0) {
					if (d[x + 2][y] > d[x][y] + 1) {
						d[x + 2][y] = d[x][y] + 1;
						v.push_back({ x + 2,y });
					}
				}
				if (wall[x - 1][y] == 0) {
					if (d[x - 2][y] > d[x][y] + 1) {
						d[x - 2][y] = d[x][y] + 1;
						v.push_back({ x - 2,y });
					}
				}
				if (wall[x][y+1] == 0) {
					if (d[x][y+2] > d[x][y] + 1) {
						d[x][y+2] = d[x][y] + 1;
						v.push_back({ x,y+2 });
					}
				}
				if (wall[x][y-1] == 0) {
					if (d[x][y-2] > d[x][y] + 1) {
						d[x][y-2] = d[x][y] + 1;
						v.push_back({ x,y-2 });
					}
				}
			}
		}
		if (d[2 * h - 1][2 * w - 1] == (int)MOD)cout << 0 << endl;
		else cout << d[2 * h - 1][2 * w - 1] << endl;
	}
	return 0;
}


Measured memory_bytes: 3132
using System;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] In = Console.ReadLine().Split(' ');
            int n = int.Parse(In[0]);
            int d = int.Parse(In[1]);
            int cnt =0;
            while (n > 0)
            {
                n -= (2 * d + 1);
                cnt++;
            }
            Console.WriteLine(cnt);
        }
    }
}


Measured memory_bytes: 27156
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut scan = Scanner::new(cin);

    let n = scan.read::<i32>();
    let mut s = vec![vec![];3];
    for i in 0..3 {s[i] = scan.read_chars();}
    let mut t = vec![];
    for i in 0..n {
        let ith = vec![s[0][uz(i)], s[1][uz(i)], s[2][uz(i)]];
        let hmap = count(&ith);
        let m = hmap.iter().map(|(_, &k)| k).max().unwrap();
        if m == 1 {
            t.push(s[0][uz(i)]);
        } else {
            t.push(hmap.iter().filter(|&(_, &k)| k == m).map(|(&c, _)| c).collect::<Vec<char>>()[0]);

        }
    }
    let mut cnt = 0;
    for i in 0..3 {
        cnt += diffcnt(&s[i], &t);
    }
    println!("{}", cnt);
}

fn diffcnt(a: &[char], b: &[char]) -> i32 {
    let mut cnt = 0;
    for i in 0..a.len() {
        if a[i] != b[i] {cnt+=1}
    }
    cnt
}

#[allow(dead_code)]
fn count<T: Eq + std::hash::Hash + Clone>(slice: &[T]) -> std::collections::HashMap<T, usize> {
    let mut hmap = std::collections::HashMap::new();
    for item in slice {
        *hmap.entry(item.clone()).or_insert(0) += 1;
    }
    hmap
}

// region template
#[allow(dead_code)]
fn uz(i: i32) -> usize { i as usize }

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read_opt<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn read<T: FromStr>(&mut self) -> T {
        self.read_opt().unwrap()
    }

    fn read_chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}
// endregion


Measured memory_bytes: 4352
import java.io.*;
import java.math.*;
import java.util.*;





public class Main {

    static MyScanner in = new MyScanner();
    static   PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    int N;
    static int max = 200001;
    static int [] dr = {1,-1,0,0};
    static int [] dc={0,0,-1,1};
    public static void main(String args[]) throws IOException {
            int N = in.nextInt();
            BitSet bs = new BitSet(N+1);
            int [] n = new int[N+1];
            for(int i=1;i<=N;i++)
            n[i] = in.nextInt();
            bs.set(1,true);
            int point =1;
            int count =0;
            while(!bs.get(2)&&count<100000){
                    count++;
                    bs.set(point, false);
                    point = n[point];
                    bs.set(point,true);
            }
           // System.out.println(point);
            System.out.println(count!=100000?count:-1);
        out.flush();
        }
       static boolean isEven(long a){
            return (a&1)==0;
        }
       static  void swap (int a, int b){

        int temmp = b;
        b=a;
        a = temmp;
        }
        static boolean same(int [] arr,int [] temp){
            Arrays.sort(arr);
           Arrays.sort(temp);
            for(int i=0;i<arr.length;i++){
                if(temp[i]!=arr[i])
                return false;
            }
            return true;
        }

 
  


    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
   
        public MyScanner() {
           br = new BufferedReader(new InputStreamReader(System.in));
        }
   
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
   
        int nextInt() {
            return Integer.parseInt(next());
        }
   
        long nextLong() {
            return Long.parseLong(next());
        }
   
        double nextDouble() {
            return Double.parseDouble(next());
        }
   
        String nextLine(){
            String str = "";
        try {
           str = br.readLine();
        } catch (IOException e) {
           e.printStackTrace();
        }
        return str;
        }
  
     }
}

Measured memory_bytes: 35376
import numpy as np


def solve():
    dists = np.zeros(n, dtype=int)
    for i in range(n):
        dists[i] = abs(a[(i+1)%n]-a[i%n])
        dists[i] = min(dists[i], k-dists[i])
    ans = k - np.max(dists)
    print(ans)
    return




k, n = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]
solve()

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

using namespace std;

int main() {
	long long n; cin >> n;
	vector<long long> ret;
	for (long long i = 1; i * i <= n; ++i)
		if (n % i == 0)
			ret.push_back(i);
	long long ans = 1e18;
	for (long long i = 0; i < ret.size(); ++i) {
		long long a = ret[i], b = n / a;
		ans = min(ans, a + b - 2);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int i, N, A[100001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(A[i]));

	int B[100001];
	for (i = 1; i <= N; i++) B[A[i]] = i;
	for (i = 1; i <= N; i++) printf("%d ", B[i]);
	printf("\n");
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 1536
/// Find the maximum product of subsequences  of size k
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define pb push_back
#define inf 1000000000000000000
using namespace std;
int main()
{
    ll i,j,k,n,s=0;
    cin>>n;
    cin>>k;
    ll K=k;
    vector<ll>neg,pos,zero;
    vector<pair<ll,ll> >vec;
    ll arr[n];
    for(i=0; i<n; i++)
    {
        cin>>arr[i];
        if(arr[i]>0)
        {
            pos.pb(arr[i]);
            s=1;
        }
        else if(arr[i]<0)
        {
            neg.pb(abs(arr[i]));
            s=-1;
        }
        else
        {
            zero.pb(arr[i]);
            s=1;
        }
        vec.pb(make_pair(abs(arr[i]),s));
    }
    ll idp=pos.size()-1;
    ll idn=neg.size()-1;
    sort(pos.begin(),pos.end());
    sort(neg.begin(),neg.end());
    sort(vec.begin(),vec.end());
    ll ans=1;
    if(k%2)
    {
        if(pos.size()>0)
        {
            ans=((ans*pos[idp])%mod+mod)%mod;
            idp--;
            k--;
        }
    }
    /// as k is even so k will be zero if enough positive or negative pair is present here
    while(k&& (idp>0||idn>0))
    {
        ll a=-inf;
        ll b=-inf;
        if(idp>=1)
            a=pos[idp]*pos[idp-1];
        if(idn>=1)
            b=neg[idn]*neg[idn-1];
        if(a>b)
        {
            ans=(ans%mod*(a%mod+mod)%mod)%mod;
            idp=idp-2;
            k=k-2;
        }
        else
        {
            ans=(ans%mod*(b%mod+mod)%mod)%mod;
            idn=idn-2;
            k=k-2;
        }
    }
    if(k)
    {
        if(zero.size())
            ans=0;
        else
        {
            ans=1;
            for(i=0; i<K; i++)
                ans=(ans%mod*(((vec[i].first*vec[i].second)%mod)+mod)%mod)%mod;
        }
    }
    cout<<ans;
return 0;

}


Measured memory_bytes: 10836
using System;

class Program
{
	static void Main()
	{
		string S = "";
		int D = int.Parse(Console.ReadLine());
		for (int i = 1; i <= D; i++)
		{
			int x = i;
			if (x % 3 == 0)
			{
				S += " " + i;
			}
			else
			{
				while (x != 0)
				{
					if (x % 10 == 3)
					{
						S += " " + i;
						break;
					}
					x /= 10;
				}
			}
		}
		Console.WriteLine(S);
	}
}

Measured memory_bytes: 15856
s = gets.chomp.split("").map(&:to_s)
t = gets.chomp.split("").map(&:to_s)
s_tmp = []
t_tmp = []
("a".."z").each do |alphabet|
  s_tmp << s.each_index.select {|i| s[i] == alphabet}
  t_tmp << t.each_index.select {|i| t[i] == alphabet}
end
s_tmp.sort!
t_tmp.sort!
if s_tmp == t_tmp
  puts "Yes"
else
  puts "No"
end

Measured memory_bytes: 29200
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;



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

  map<char, int> st;
  for(int i=0;i<s.size();i++){
    st[s[i]] = 0;
  }

  for(int i=0;i<s.size();i++){
    st[s[i]]++;
  }

  for(int i=0;i<s.size();i++){
    if(st[s[i]]%2 == 1){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  Int ans=a[0];
  for(Int i=0;i<n;i++) ans=__gcd(ans,a[i]);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1152
import java.util.Scanner;

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

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();

		long ans = 0;
		for(int b=1; b<=n; b++) {
			int p = n/b;
			int r = n%b;
			ans += Math.max(0, b-k) * p + Math.max(0, r-(k-1));
		}
		if(k==0) {
			ans -= n;
		}
		System.out.println(ans);
		sc.close();
	}

}


Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#include<iomanip>
#include<map>
#define int long long 
using namespace std;

signed main() {
	int N;
	cin >> N;
	int cnt;
	int count = -2;
	vector<int> vec(100000);
	for(int i = 1;i < 1e5;i++) {
		if(N % count != 0) {
			vec.at(i - 1) = 1;
		}
		else {
			vec.at(i - 1) = 0;
		}
		N -= count / -2 * vec.at(i - 1);
		if(N == 0) {
			cnt = i;
			break;
		}
		count = count * -2;
	}	
	for(int i = 0;i < cnt;i++) {
		cout << vec.at(cnt - i - 1);
	}
	cout << endl;
}

Measured memory_bytes: 1024
N = list(input())
ans = "No"
before_num = N[0]

tmp = 1
for i in range(1, len(N)):
    if N[i] == before_num:
        tmp += 1
        if tmp == 3:
            ans = "Yes"
            break
    else:
        tmp = 1
        before_num = N[i]

print(ans)


Measured memory_bytes: 2940
#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
	ll n;
	cin >> n;
	if (n % 2 == 0)
	{
		ll x = (n / 2)*(n / 2);
		cout << x << endl;
	}
	else
	{
		ll x = (n / 2)*(n / 2 + 1);
		cout << x << endl;
	}
	return 0;
}


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

int main() {

int src;
int a, b, c;

cin >> src;
a = src / 100;
b = (src - a*100) / 10;
c = (src - a*100 - b*10) / 1;
cout << a+b+c << endl;
}



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

int main(){
    int a[10005];
    int q[505];
    int data_num;
    scanf("%d", &data_num);
    for(int i=0; i<data_num; i++){
        scanf("%d", &a[i]);
    }
    int query_num;
    scanf("%d", &query_num);
    for(int i=0; i<query_num; i++){
        scanf("%d", &q[i]);
    }
    
    int find = 0;
    for(int i=0; i<query_num; i++){
        for(int j=0; j<data_num; j++){
            if(q[i]==a[j]){
                find++;
                break;
            }
        }
    }
    printf("%d\n", find);
}



Measured memory_bytes: 2100
n = int(input())
l = list(map(int,input().split()))
dp = [0]*n
dp[1] = abs(l[1]-l[0])
for i in range(2,n):
    dp[i] = min(dp[i-2]+abs(l[i-2]-l[i]),dp[i-1]+abs(l[i-1]-l[i]))
print(dp[n-1])

Measured memory_bytes: 13928
#include "stdio.h"
int fun(int n)
{
    int c=0;
    while(n/=2)  // n=n/2
    {
        c++;
    }
    return c;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int i,max=0,t=1;
        for(i=1;i<=n;i++)
            if(fun(i)>max)
            {
                max=fun(i);
                t=i;
            }
        printf("%d\n",t);
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
#define pb push_back
using ll = long long;
using ld = long double;
constexpr ll mod = 1000000007LL;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, m;
	cin >> n >> m;
	vector<ll> x(n);
	vector<ll> y(m);
	rep(i,n) cin >> x[i];
	rep(i,m) cin >> y[i];
	ll sum1 = 0;
	ll sum2 = 0;
	ll acm1 = 0;
	ll acm2 = 0;
	rep(i,n) {
		sum1 += i * x[i] - acm1;
		sum1 %= mod;
		acm1 += x[i];
	}
	rep(i,m) {
		sum2 += i * y[i] - acm2;
		sum2 %= mod;
		acm2 += y[i];
	}
	cout << (sum1 * sum2) % mod << endl;
	return 0;
}

Measured memory_bytes: 1920
s=input()
e=[]
for i in range(len(s)):
    if s[i]=="1":
        e.append("1")
    elif s[i]=="0":
        e.append("0")
    else:
        if not len(e)==0:
            e.pop(-1)
o=""
for i in e:
    o=o+i
print(o)

Measured memory_bytes: 3060
#include<stdio.h>
int main(){
	long n,m,l,i,j,k,sum=0,a[100][100],b[100][100];
	scanf("%ld %ld %ld",&n,&m,&l);
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			scanf("%ld",&a[i][j]);
		}
	}
	for(j=0;j<m;j++){
		for(k=0;k<l;k++){
			scanf("%ld",&b[j][k]);
		}
	}
	for(i=0;i<n;i++){
		for(k=0;k<l;k++){
			for(j=0;j<m;j++){
				sum+=a[i][j]*b[j][k];
			}
			printf("%ld",sum);
			sum=0;
			if(k!=l-1){
				printf(" ");
			}else{
				printf("\n");
			}
		}
	}
}


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

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  rep(num, 1000) {
    rep(i,n) {
      if (s[i]-'0' != num/100) continue;
      for (int j = i+1; j < n-1; ++j) {
        if (s[j]-'0' != num/10 % 10) continue;
        for (int k = j+1; k < n; ++k) {
          if (s[k]-'0' == num % 10) {
            ans++; break;
          }
        }
        break;
      }
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=sorted(p);c+=x;b+=y;j-=1
print((c+sum(sorted(b)[:j]),'Impossible')[k>n]*(k>0))

Measured memory_bytes: 138924
import java.util.Scanner;

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



Measured memory_bytes: 33128
n,k=map(int,input().split())
d=list(map(int,input().split()))

def f(x):
    x=str(x)
    x=list(x)
    for i in x:
        if int(i) in d:
            return False
    return True

ans=n

while not f(n):
    n+=1
print(n)


Measured memory_bytes: 73444
n = int(input())
a = [int(input())-1 for _ in range(n)]
visit=[False]*n
cnt=0
nxt=0
for _ in range(n):
    visit[nxt]=True    

    #ボタン2にたどり着いた
    if nxt==1:
        break

    nxt=a[nxt]

    #ループしている到達不能！
    if visit[nxt]:
        cnt=-1
        break

    cnt+=1
    
print(cnt)

Measured memory_bytes: 7852
// E

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll mod=1e9+7;

int main(){
  int N,A[100000];
  cin>>N;
  for (int i(0);i<N;i++) cin>>A[i];
  int dp[100001][3] = {0};

  for (int i(1);i<=N;i++){
    bool flag = true;
    for (int j(0);j<3;j++){
      if (dp[i-1][j] == A[i-1] && flag == true){
        dp[i][j] = dp[i-1][j]+1;
        flag = false;
      } else {
        dp[i][j] = dp[i-1][j];
      }
    }
    sort(dp[i],dp[i]+3,greater<int>());
  }

  ll cnt(1);
  for (int i(0);i<N;i++){
    int cnti(0);
    for (int j(0);j<3;j++){
      if (A[i] == dp[i][j]) cnti++;
    }
    cnt*= cnti;
    cnt%=mod;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 1792
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] n = new int[3];
		for(int i = 0; i < 3; i++) {
			n[i] = sc.nextInt();
		}
		Arrays.sort(n);
		n[2] -= n[1];
		n[1] -= n[0];
		System.out.println(n[1]+n[2]);
	}
}


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

#define ll long long
//~ #define endl '\n'

void solve(){
	ll n, d, cnt = 0; cin>>n>>d;
	for(int i = 0; i<n; i++){
		ll a, b; cin>>a>>b;
		if((a * a + b * b) <= (d * d)) cnt++;
	}
	cout<<cnt<<endl;
}

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


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

int main(){
	
	int N,T,A; 
	cin >>N >>T >>A;
	
	vector<int> vec(N);
	
	for(int i=0; i<N; i++){
		
		cin >>vec.at(i);
		
	}
	
	vector<pair<double,int>> p(N);
	
	for(int i=0; i<N; i++){
		
		p[i].first=abs(T-vec.at(i)*0.006-A);
		p[i].second=i;
		
	}
	
	sort(p.begin(),p.end());
	cout <<p[0].second+1 <<endl;
	
}



Measured memory_bytes: 256
def main():
    n=int(input())
    s=input()
    s=s[1:]+s[0]
    def check(i):
        if ans[-1]=="S":
            if s[i]=="o":
                ans.append(ans[-2])
            else:
                if ans[-2]=="S":
                    ans.append("W")
                else:
                    ans.append("S")
        else:
            if s[i]=="x":
                ans.append(ans[-2])
            else:
                if ans[-2]=="S":
                    ans.append("W")
                else:
                    ans.append("S")
    ans=["S","S"]
    for i in range(n):
        check(i)
    if ans[0]==ans[-2] and ans[1]==ans[-1]:
        print("".join(ans[:-2]))
        return 0
    ans=["S","W"]
    for i in range(n):
        check(i)
    if ans[0]==ans[-2] and ans[1]==ans[-1]:
        print("".join(ans[:-2]))
        return 0
    ans=["W","S"]
    for i in range(n):
        check(i)
    if ans[0]==ans[-2] and ans[1]==ans[-1]:
        print("".join(ans[:-2]))
        return 0
    ans=["W","W"]
    for i in range(n):
        check(i)
    if ans[0]==ans[-2] and ans[1]==ans[-1]:
        print("".join(ans[:-2]))
        return 0
    print(-1)
main()

Measured memory_bytes: 4996
#include<stdio.h>
#define N_MAX 250
short m,n,f[N_MAX+2],d[N_MAX],ij[N_MAX + 2][N_MAX + 2],used[N_MAX + 2],s[N_MAX + 2][N_MAX + 2];

short min(short i,short j){return(i<j)?i:j;}

void dijkstra(short x){
    short u,v;
    for(u=0;u<n+2;u++)used[u]=0,s[x][u]=1;
    s[x][x] = 0;
    for(;;){
        v = -1;
        for(u=0;u<n+2;u++)if(!used[u] && (v < 0 || s[x][u] < s[x][v]))v = u;
        if(v < 0)break;
        used[v] = 1;
        for(u=0;u<n+2;u++)s[x][u]=min(s[x][u],s[x][v]+1-ij[v][u]);
    }
    return;
}

short solve(short x){
    short i;
    dijkstra(x);
    if(s[x][n+1])return 0;
    f[x] = 1;
    for(i=0;i<=n;i++){
        if(!f[i] && !s[x][i] && !solve(i))
        return 0;
    }
    return 1;
}

void graph(void){
    short i,j,k;
    for(i=0;i < n + 2;i++){
        for(j=0;j < n + 2;j++)ij[i][j]=0;
        for(j=1;j<=m;j++){
            k = i + j;
            if(k > n)
                k = n + 1;
            else{
                k += d[k - 1];
                if(k < 0)k = 0;
            }
            ij[i][k] = 1;
        }
    }
    return;
}

int main(void){
    short i;
    while(scanf("%hd",&m),m){
        scanf("%hd",&n);
        for(i=0;i<n;i++)d[i]=0,scanf("%hd",d+i);
        for(i=0;i<n+2;i++)f[i]=0;
        graph();
        puts(solve(0)?"OK":"NG");
    }
    return 0;
}

Measured memory_bytes: 832
import java.util.*;
public class Main {
	public static void main(String[] args){
      	
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int happy = 0;
		if (X<500) {
			while (X>=5) {
				X -= 5;
				happy += 5;
			}			
		} else {
			while (X>=500) {
				X -= 500;
				happy += 1000;
			}
			while (X>=5) {
				X -= 5;
				happy += 5;
			}
		}

		System.out.println(happy);
      	sc.close();
    }
		
		
}

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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")
int res[1000001];

int main()
{
	int N;
	cin >> N;
	vec(A);
	fx(N) {
		vecp(A);
		res[A[x]]++;
	}
	int ans = 0;
	fx(N) {
		for (int i = 1; i * i <= A[x]; i++) {
			if (A[x] % i == 0) {
				if (i == 1) {
					if (A[x]==1) {
						if (res[A[x] / i] > 1) {
							ans++;
							break;
						}
					}
					else {
						if (res[i] > 0 || res[A[x] / i] > 1) {
							ans++;
							break;
						}
					}

				}
				else {
					if (res[i] > 0 || res[A[x] / i] > 0) {
						ans++;
						break;
					}
				}

			}
		}
	}
	ce(N - ans)
    return 0;
}



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

int GCD(int a, int b);

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++)
        cin >> A[i];

    vector<int> L(N), R(N);
    for(int i = 0; i < N - 1; i++){
        L[i + 1] = GCD(L[i], A[i]);
    }
    for(int i = N - 1; i >= 1; i--){
        R[i - 1] = GCD(R[i], A[i]);
    }

    int ans = 1;
    for(int i = 0; i < N; i++){
        ans = max(ans, GCD(L[i], R[i]));
    }

    cout << ans << endl;

    return 0;
}

int GCD(int a, int b) {
  if (b == 0) 
    return a;  
  return GCD(b, a % b);
}

Measured memory_bytes: 1408
#include <stdio.h>

int doubleup(int num,int goal);

int main()
{
	int n,m,i,j,k,l,o,p,s,flag,t=1;
	int ans=0;
	int sw[10][10]={0};
	int plst[11];
	
	scanf("%d %d",&n,&m);
	
	for(i=0;i<m;i++)
	{
		scanf("%d",&k);
		for(j=0;j<k;j++)
		{
			scanf("%d",&s);
			sw[i][s-1]=1;
		}
	}
	for(i=0;i<m;i++)
	{
		scanf("%d",&p);
		plst[i]=p;
	}
	for(j=0;j<n;j++)
	{
		t*=2;
	}
	
	for(l=0;l<t;l++)//2^10
	{
		flag=1;
		//printf("\n%d %d %d %d %d %d %d %d %d %d",l/512&1,l/256&1,l/128&1,l/64&1,l/32&1,l/16&1,l/8&1,l/4&1,l/2&1,l/1&1);
		for(i=0;i<m;i++)
		{
			flag=flag & ((
			(l/1&1&sw[i][0])^
			(l/2&1&sw[i][1])^
			(l/4&1&sw[i][2])^
			(l/8&1&sw[i][3])^
			(l/16&1&sw[i][4])^
			(l/32&1&sw[i][5])^
			(l/64&1&sw[i][6])^
			(l/128&1&sw[i][7])^
			(l/256&1&sw[i][8])^
			(l/512&1&sw[i][9])
			)==plst[i]);
		}
		//printf(" flag:%d",flag);
		if(flag)ans++;
	}
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 128
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=20;
char str[maxn];
const int INF=1e9;
const double eps=1e-9;
inline int read(){
	int x=0,flag=1;
	char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')flag=-1,ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*flag;
}
int main(){
	int i,j,k,m,n;
	n=read();m=read();k=read();
	for(i=0;i<=n;i++)
		for(j=0;j<=m;j++)
			if(i*m+j*n-2*i*j==k){
				puts("Yes");
				return 0;
			}
	puts("No");
	return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let mut grid = vec![vec![]; 3];
    grid[0] = read_vec::<usize>();
    grid[1] = read_vec::<usize>();
    grid[2] = read_vec::<usize>();
    let mut checked = vec![vec![false; 3]; 3];
    let n = read::<usize>();
    for i in 0..n {
        let b = read::<usize>();
        for y in 0..3 {
            for x in 0..3 {
                if grid[y][x] == b {
                    checked[y][x] = true;
                }
            }
        }
    }
    'oy: for y in 0..3 {
        for x in 0..3 {
            if !checked[y][x] {
                continue 'oy;
            }
        }
        println!("Yes");
        return;
    }
    'ox: for x in 0..3 {
        for y in 0..3 {
            if !checked[y][x] {
                continue 'ox;
            }
        }
        println!("Yes");
        return;
    }
    if checked[0][0] && checked[1][1] && checked[2][2] {
        println!("Yes");
        return;
    }
    if checked[0][2] && checked[1][1] && checked[2][0] {
        println!("Yes");
        return;
    }
    println!("No");
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys
from collections import defaultdict

sys.setrecursionlimit(pow(2, 31) - 1)

# from typing import Dict, List, Optional, Set, Tuple

# def dfs(vertex: int, succ: Dict[int, List[int]], dp: Dict[int, int]) -> int:
def dfs(vertex, succ, dp):
    if vertex in dp:
        return dp[vertex]
    length = 0
    for s in succ[vertex]:
        length = max(length, 1 + dfs(s, succ, dp))
    dp[vertex] = length
    return length


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, _nb_edges) -> int:
    succ = defaultdict(list)
    for s, d in values:
        succ[s].append(d)
    # all edges have a 0 length path starting at the edge
    dp = defaultdict(lambda: -1)
    for vertex in frozenset(succ.keys()):
        if vertex in dp:
            dp[vertex] = max(dp[vertex], dfs(vertex, succ, dp))
        else:
            dp[vertex] = dfs(vertex, succ, dp)
    return max(dp.values())


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


if __name__ == "__main__":
    do_job()


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

int main(){
  int n;
  cin >> n;
  vector<int> X(n);
  rep(i,n) cin >> X[i];
  int ans = INF;
  rep(i,100){
    int tot = 0;
    rep(j,n){
      tot += pow(X[j]-i,2);
    }
    if(tot<ans)ans = tot;
  }
  cout << ans << endl;
  return 0;
}


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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// ====================================================================

int main() {
  vector<int> v(2020);

  int n, x;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    v[x] = i;
  }

  int m, a;
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> a;
    int t = 0;
    while (v[t] != a && t < 2020) t++;
    if (t == 2019 || v[t + 1]) continue;
    v[t + 1] = v[t];
    v[t] = 0;
  }

  for (int i = 1; i <= n; i++) {
    int t = 0;
    while (v[t] != i && t < 2020) t++;
    cout << t << endl;
  }
}



Measured memory_bytes: 3112
n,k,c=map(int,input().split())
#n日中k日働く。働いたらc日働かない

s=list(input())

#Xの時、i日後には働かない

ll=[]
rr=[]

day=0
while day<n:
    if s[day]=="o":
        ll.append(day)
        day+=(c+1)
    else:
        day+=1
    if len(ll)>=k:
        break

day=n-1
while 0<=day:
    if s[day]=="o":
        rr.append(day)
        day-=(c+1)
    else:
        day-=1
    if len(rr)>=k:
        break
        
rr=rr[::-1]
#print(ll)
#print(rr)

for i in range(k):
    if ll[i]==rr[i]:
        print(ll[i]+1)

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

using namespace std;

int main()
{
   string s;
   cin >> s;
   
   if (s.length()==3) {
       cout << s[2] << s[1] << s[0] <<endl;
   }
   else
   {
             cout << s[0] << s[1]  <<endl; 
   }
   
   
   return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int b[] = new int[n-1];
		for(int i = 0; i < n-1; i++){
			b[i] = sc.nextInt();
		}
		int sum = b[0];
		for(int i = 1; i < n-1; i++){
			sum+=Math.min(b[i-1],b[i]);
		}
		sum+=b[n-2];
		System.out.print(sum);
	}
}


Measured memory_bytes: 21844
// inputに入力データ全体が入る
function Main(input) {
  var N = parseInt(input[0],10);
  var array = input.slice(1).map(a =>
    parseInt(a, 10)
  );
  var orgArray = array.map(a=>a);
  var sortAarry = array.sort((a, b) => b - a);

  for(var i = 0; i < N; i++){
    if(orgArray[i] == sortAarry[0]){
      console.log(sortAarry[1]);
    }
    else{
      console.log(sortAarry[0]);
    }
  }
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

Measured memory_bytes: 60156
n = int(input())
a = [list(map(int, input().split())) for k in range(n)]
a.sort(key = lambda x: x[1])
worktime = 0
deadline = 0
for i in range(n):
    if worktime <= deadline:
        worktime += a[i][0]
        deadline = a[i][1]
        if worktime <= deadline and i == n-1:
            print('Yes')
        elif worktime > deadline and i == n-1:
            print('No')
        else:
            pass
    else:
         print('No')
         break


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

const int MAX_V = 100000;
int par[MAX_V];
int depth[MAX_V];
int num[MAX_V];

void init(int n) {
    for(int i = 0; i < n; i++) {
        par[i] = i;
        depth[i] = 0;
        num[i] = 1;
    }
}

int root(int x) {
    if (par[x] == x) return x;
    else return par[x] = root(par[x]);
}

void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return;

    num[x] += num[y];
    num[y] = num[x];

    if (depth[x] < depth[y]) par[x] = y;
    else {
        par[y] = x;
        if (depth[x] == depth[y]) depth[x]++;
    }
}

bool same(int x, int y) {
    return root(x) == root(y);
}

int get_num(int x) {
    return num[root(x)];
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> done(m + 1, -1);
    init(n);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int l;
            cin >> l;

            if (done.at(l) != -1) unite(i, done.at(l));
            else done.at(l) = i;
        }
    }
    
    if (get_num(0) == n) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

#define MAXN 100005

const int inf = 2e9+10;

int h[MAXN];

int dp[MAXN];
int k;

int main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);
    
#ifdef NOTINAIR
    freopen("stdin","r",stdin);
#endif    
    int n;cin>>n>>k;


    for(int i=1;i<=n;i++){
    
        cin>>h[i];    

    }

    
    for(int i=2;i<=n;i++){
        int minn=inf;
        for(int j=1;j<=k&&j<i;j++){

            minn = min(minn,dp[i-j] + abs(h[i] - h[i-j]));
            //cerr<<"dp "<<dp[i-j]<<endl;
        }
       dp[i] = minn; 
       //cerr<<i<<" "<<dp[i]<<endl;
    }
    

    cout<<dp[n]<<endl; 

}


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

int main(){
  int n,n1,n10,n100;
  cin >>n;
  n1 = n % 10;
  n10 = ((n-n1)/10)%10;
  n100 = ((n-n1-n10)/100)%10;
  
  if(n1==1){
    n1=9;
  }
  else if(n1==9){
    n1=1;
  }
  
  if(n10==1){
    n10=9;
  }
  else if(n10==9){
    n10=1;
  }
  
  if(n100==1){
    n100=9;
  }
  else if(n100==9){
    n100=1;
  }
  
  n=n100*100+n10*10+n1;
  cout<<n;
  return 0;
}

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

using namespace std;
#define INP "solve"
#define OUT "solve"
const int QQ = 3e5 + 10;
const int maxN = 3e5 + 10;
const int maxM = 3e5 + 10;
const int oo = 1e9;
const int module = 1e9 + 7;

void doc() {
    freopen(INP ".inp","r",stdin);
    freopen(OUT ".out","w",stdout);

}

void solve() {
    int n, d;
    cin >> n >> d;
    int L = 2 * d + 1;
    int Res = 1;
    while (L < n) {
        Res++;
        L += 2 * d + 1;
    }
    cout << Res;
}
int main(int argc,char *argv[]) {
    //srand(time(nullptr));
    ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
   // doc();
    solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<sstream>
#include<list>
#include<climits>

using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define nrep(i,i0,n) for(int i=(i0);i<(int)(n);++i)
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vii;
typedef long long ll;


int main(){
	int n;
	scanf("%d",&n);
	int a[100010];
	rep(i,n)scanf("%d",&a[i+1]);
	set<int> st;
	int cur=1;
	int cnt=0;
	bool flag=false;
	while(st.find(cur)==st.end()){
		st.insert(cur);
		cnt++;
		cur=a[cur];
		if(cur==2){
			flag=true;
			break;
		}
	}
	int ret=flag?cnt:-1;
	printf("%d\n",ret);
	return 0;
}



Measured memory_bytes: 5376
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    //cout.precision(10);
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    long long sum[100100];
    sum[0] = a[0];
    for(int i = 1; i < n; i++){
        sum[i] = sum[i - 1] + a[i];
    }
    for(int i = n - 2; i >= 0; i--){
        if(sum[i] * 2 < a[i + 1]){
            cout << n - i - 1 << endl;
            return 0;
        }
    }
    cout << n << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep0(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define mREP(i,a,b) for (int i = a; i > (b); --i)
#define all(x) (x).begin(),(x).end()
const int INF = 1000000007;
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int v[] = {-1,1,3,1,2,1,2,1,1,2,1,2,1,};
int main(){
    int a,b;
    cin>>a>>b;
    cout<<(a-1)*(b-1)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX_INT 1000000000
#define MAX 100

int n,a[MAX][MAX];

int prim(void);

int main(){
  int e;
  int i,j;
  scanf("%d",&n);

  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      scanf("%d",&e);
      if(e == -1) a[i][j] = MAX_INT;
      else a[i][j] = e;
    }
  }

  printf("%d\n",prim());

  return 0;
}

int prim(){
  int s,small,sum = 0;
  int pa[MAX],min[MAX],judge[MAX];
  int i,j;

  for(i = 0; i < n; i++){
    min[i] = MAX_INT;
    pa[i] = -1;
    judge[i] = 0;
  }

  min[0] = 0;

  for(;;){

    small = MAX_INT;
    s = -1;

    for(i = 0; i < n; i++){
      if(small > min[i] && judge[i] != 2){
	s = i;
	small = min[i];
      }
    }

    if( s == -1) break;

    judge[s] = 2;

    for( j = 0; j < n; j++){
      if(judge[j] != 2 && a[s][j] != MAX_INT){
	if(min[j] > a[s][j]){
	  min[j] = a[s][j];
	  pa[j] = s;
	  judge[j] = 1;
	}
      }
    }
  }
  for(i = 0; i < n; i++){
    if(pa[i] != -1) sum += a[i][pa[i]];
  }

  return sum;
}

Measured memory_bytes: 636
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <random>

using ll = long long int;
int N;
constexpr int MAXN = 200001;
std::vector<ll> A;
std::vector<ll> B;

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
#define rep(i, a, b) for(int i = (a); i < (b); ++i )
#define rrep(i, a, b) for(int i = (a); i > (b); --i )
#define REP(i, a, b) for(int i = (a); i <= (b); ++i )
#define RREP(i, a, b) for(int i = (a); i >= (b); --i )

int main() {
    cin >> N;
    A.resize(N);
    B.resize(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    ll ans = 0;
    for (ll v = (1 << 28); v != 0; v >>= 1) {
        rep(i, 0, N) A[i] &= (v * 2 - 1);
        rep(i, 0, N) B[i] &= (v * 2 - 1);
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        int cur = 0;
        int j = 0;
        int k = 0;
        int l = 0;
        for (int i = N - 1; i >= 0; i--) {
            while (j < N && (A[i] + B[j]) < 1 * v) j++;
            while (k < N && (A[i] + B[k]) < 2 * v) k++;
            while (l < N && (A[i] + B[l]) < 3 * v) l++;
            cur += (k - j) + (N - l);
        }
        if (cur & 1) {
            ans |= v;
        }
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 3328
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>

int n,d,x;
int a[100];

int main(void){
	scanf("%d", &n);
	scanf("%d %d", &d, &x);
	for(int i=0;i<n;i++){
		scanf("%d", &a[i]);
		x += (d-1)/a[i];
		x++;
	}
	printf("%d", x);
	
}


Measured memory_bytes: 128
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
map<ll, ll> mmap;
int N, M;
ll A, B, C;
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &A);
		mmap[-A]++;
	}
	for (int i = 0; i < M; i++) {
		scanf("%lld %lld", &B, &C);
		mmap[-C] += B;
	}
	ll sol = 0;
	ll cnt = N;
	for (auto it = mmap.begin(); it != mmap.end(); it++) {
		ll cost = min(cnt, it->second);
		if (cost == 0) break;


		sol -= it->first*cost;
		cnt -= cost;
	}
	printf("%lld\n", sol);
}

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

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    if (a == 1) a = 14;
    if (b == 1) b = 14;
    if (a > b) cout << "Alice" << endl;
    else if (b > a) cout << "Bob" << endl;
    else cout << "Draw" << endl;
    return 0;
}

Measured memory_bytes: 256