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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

class SegmentTree
{
  public:
    SegmentTree(int n)
    {
        int c = 1;
        while (c < n)
            c <<= 1;
        N = c;
        node.resize(2 * N - 1);
        REP(i, node.size())
        {
            node[i] = n;
        }
    }

    void set(int l, int r, int v, int k = 0, int tl = 0, int tr = -1)
    {
        if (tr == -1)
            tr = N - 1;
        if (tr < l || r < tl)
            return;

        if (l <= tl && tr <= r)
        {
            node[k] = std::min(v, node[k]);
            return;
        }
        set(l, r, v, 2 * k + 1, tl, (tl + tr) / 2);
        set(l, r, v, 2 * k + 2, (tl + tr) / 2 + 1, tr);
    }

    int get(int n)
    {
        int k = N - 1 + n;
        int min = node[0];
        while (k > 0)
        {
            min = std::min(min, node[k]);
            k = (k - 1) / 2;
        }
        return min;
    }

  private:
    int N;
    vector<int> node;
};

ll A[200005];
//! index i以降の和
ll S[200005];

int main()
{
    int N;
    cin >> N;
    REP(i, N)
    {
        cin >> A[i];
    }
    S[N] = 0;
    SegmentTree seg(N);
    ll sum = 0;
    for (ll i = N - 1; i >= 0; --i)
    {
        ll a = A[i];
        ll index = seg.get(a - 1);
        S[i] = S[index] + a * (index - i);
        sum += S[i];
        seg.set(a - 1, N - 1, i);
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 5376
import math
n=int(input());
arr=[]
j=2
while j*j<=n:
	cnt=0
	while n%j==0:
		cnt=cnt+1
		n=n/j
	if cnt!=0:
		arr.append(cnt)
	j=j+1
if n>1:
	arr.append(1)
ans=int(0)
for i in arr:
	ans=ans+int((math.sqrt(1+8*i)-1)/2)
print(ans)

Measured memory_bytes: 9192
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
const int MAX=1e5;

int main(){
	string S;
	cin>>S;
	lli l=(lli)S.length();
	lli c[26];
  	rep(i,26)c[i]=0;
	rep(i,l){
		int t=S[i]-'a';
		c[t]++;
	}
	lli ans=l*(l-1)/2+1;
	rep(i,26){
		ans-=c[i]*(c[i]-1)/2;
	}
	cout<<ans;
}

Measured memory_bytes: 640
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    sx, sy, tx, ty = map(int, input().split())

    dy, dx = ty - sy, tx - sx
    ans = ""
    ans += dx * "R" + dy * "U"
    ans += "R" + (1 + dy) * "D" + (1 + dx) * "L" + "U"
    ans += dy * "U" + dx * "R"
    ans += "U" + (1 + dx) * "L" + (1 + dy) * "D" + "R"
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4200
#include <bits/stdc++.h>
using namespace std;
int n,j;
vector<string> s;

int dfs(int k,int f) {
  int ans=f;
  while(j<n&&k<s[j].size()) {
    int x;j++;
    if(isdigit(s[j-1][k])) x=s[j-1][k]-'0';
    else x=dfs(k+1,s[j-1][k]=='*');
    if(!f) ans+=x;
    else ans*=x;
  }
  return ans;
}

int main() {
  while(cin>>n&&n) {
    s.clear();
    for(int i=0;i<n;i++) {
      string t;
      cin >> t;
      s.push_back(t);
    }
    j=0;
    cout << dfs(0,0) << endl;
  }
}


Measured memory_bytes: 3212
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;
using P = std::pair<ll, ll>;

constexpr ll INF = 1ll<<60;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

std::string c[3];

int main()
{
  rep( i, 3 )
    std::cin >> c[i];

  rep( i, 3 )
    std::cout << c[i][i];

  std::cout << std::endl;

  return 0;
}

Measured memory_bytes: 3616
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

sf=0

for i in range(n):
  sf+=b[a[i]-1]

  if i!=0:
    if a[i]==(a[i-1]+1):
      sf+=c[a[i-1]-1]

print(sf)


Measured memory_bytes: 38328
#include<cstdio>
#include<algorithm>

using namespace std;

const int MAX_N = 50;
int n, m;
int g[MAX_N][MAX_N];
int a[MAX_N];



    
void sagasu(int num){
    for(int i = 0; i < n; i++){
        // puts("1");
        if (g[num][i] == 1 and a[i] == 0){
            // printf("%d\n", i);
            a[i] = 1;
            sagasu(i);
        }
    }
    
}

int main(){

    scanf("%d %d", &n, &m);

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

    // for(int i = 0; i < n; i++){
    //     for(int j = 0; j < n; j++){
    //         printf("%d", g[i][j]);
    //     }
    //     printf("\n");
    // }
    


    int count = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if (i > j && g[i][j] == 1){
                // printf("%d %d\n", i, j);
                g[i][j] = 0;
                g[j][i] = 0;
                fill(a, a + n, 0);
                a[0] = 1;
                sagasu(0);
                for(int k = 0; k < n; k++){
                    if (a[k] == 0){
                        count++;
                        break;
                    }
                }
                g[i][j] = 1;
                g[j][i] = 1;
            }
        }
        
    }
    printf("%d\n", count);
    
}

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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int x,a,b; cin>>x>>a>>b;
	if(b<=a) cout << "delicious" << endl;
	else if(b<=a+x) cout << "safe" << endl;
	else cout << "dangerous" << endl;
	return 0;
}


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

int main()
{
    int a,b,c;
    int n1,n2,n3;
    int tmp;

    cin >> a >> b >> c;

    n1 = a;
    n2 = b;
    n3 = c;

    if(n1 > n2)
    {
        tmp = n1;
        n1 = n2;
        n2 = tmp;
    }

    if(n2 > n3)
    {
        tmp = n2;
        n2 = n3;
        n3 = tmp;

        if(n1 > n2)
        {
            tmp = n1;
            n1 = n2;
            n2 = tmp;
        }
    }

    cout << n1 << " " << n2 << " " << n3 << endl;

    return 0;
}



Measured memory_bytes: 3092
#include<bits/stdc++.h>
#include<unordered_map>
#define ll long long
#define M 1000000007
#define pb push_back
#define fs first
#define se second
using namespace std;
int main()
{
    ll a,b,c;
    cin>>a>>b>>c;
    ll t=min(a,b);
    ll u=max(a,b);
    if(t<c && c<u)
        cout<<"Yes";
    else
        cout<<"No";
    cout<<endl;

}


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

using namespace std;

main(){
  char data[2000];
  int size;
  for(int i=0;i<2000;i++){
    scanf("%c", &data[i]);
    if(data[i]=='\n'){
      size=i;
      break;
    }
  }
  for(int i=4;i<size;i++){
    if(data[i-4]=='a' && data[i-3]=='p' && data[i-2]=='p' && data[i-1]=='l' && data[i]=='e'){
      data[i-4]='p';
      data[i-3]='e';
      data[i-2]='a';
      data[i-1]='c';
      data[i]='h';
      i+=4;
      continue;
    }
    if(data[i-4]=='p' && data[i-3]=='e' && data[i-2]=='a' && data[i-1]=='c' && data[i]=='h'){
      data[i-4]='a';
      data[i-3]='p';
      data[i-2]='p';
      data[i-1]='l';
      data[i]='e';
      i+=3;
      continue;
    }
  }
  for(int i=0;i<2000;i++){
    printf("%c", data[i]);
    if(data[i]=='\n') break;
  }
  return 0;
}

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

int main() {
	int a, b, t;
	cin >> a >> b >> t;
	int count = 0;

	for (int i = 1; i * a <= t; i++) {
		count += b;
	}
	cout << count << endl;
}


Measured memory_bytes: 3600
import java.util.*;

public class Main {
	
	public static long getCombinations(int num) {
		return ((long)num)*(num-1)/2;
	}
	
	public static int getRoot(int[][] unionArray, int index) {
		if (unionArray[index][0] == index) {
			return index;
		}
		return getRoot(unionArray, unionArray[index][0]);
	}
	
	public static int getSize(int[][] unionArray, int index) {
		if (unionArray[index][0] == index) {
			return unionArray[index][1];
		}
		return getSize(unionArray, unionArray[index][0]);
	}
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		// First position stores the parent of island i, where i = index of the position
		// Second position stores the size of the subset rooted at this island
		int[][] unionArray = new int[N][2];
		long[] inconvenience = new long[M];
		int[][] edges = new int[M][2];
		
		inconvenience[M-1] = getCombinations(N);
		
		for (int i = 0; i < N; i++) {
			unionArray[i][0] = i;
			unionArray[i][1] = 1;
		}
		
		for (int i = 0; i < M; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			edges[i][0] = A-1;
			edges[i][1] = B-1;
		}
		
		for (int i = M-1; i > 0; i--) {
			int A = edges[i][0];
			int B = edges[i][1];
			int rootA = getRoot(unionArray, A);
			int rootB = getRoot(unionArray, B);
			unionArray[A][0] = rootA;
			unionArray[B][0] = rootB;
			long convenience = 0;
			if (rootA != rootB) {
				int sizeA = unionArray[rootA][1];
				int sizeB = unionArray[rootB][1];
				if (rootA < rootB) {
					unionArray[rootB][0] = rootA;
					unionArray[rootA][1] += sizeB;
				} else {
					unionArray[rootA][0] = rootB;
					unionArray[rootB][1] += sizeA;
				}
				convenience += getCombinations(sizeA+sizeB) - getCombinations(sizeA) - getCombinations(sizeB);
			}
			inconvenience[i-1] = inconvenience[i] - convenience;
		}
		
		for (long inc : inconvenience) {
			System.out.println(inc);
		}
    }
  
}


Measured memory_bytes: 101916
#include <iostream>

template <class T>
T abs(T a) { return a > 0 ? a : -a; }

long long gcd(long long a, long long b) {
    if (a > b) {
        if (a % b == 0) return b;
        else return gcd(b, a % b);
    } else {
        if (b % a == 0) return a;
        else return gcd(a, b % a);
    }
}

int main() {
    long long n, k, a, ret;
    std::cin >> n >> k;
    std::cin >> ret;
    auto m = ret;

    for (auto i = 1ll; i < n; i++) {
        long long t;
        std::cin >> t;
        m = std::max(m, t);
        ret = gcd(ret, t);
    }

    std::cout << (k % ret == 0 && k <= m ? "POSSIBLE" : "IMPOSSIBLE") << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  vector<double> p(n);
  for(int i=0;i<n;i++) cin>>p[i];
  vector<vector<double>> dp(n+1,vector<double> (n+1,0));
  dp[0][0]=1;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      dp[i+1][j]+=dp[i][j]*(1-p[i]);
      dp[i+1][j+1]+=dp[i][j]*p[i];
    }
  }
  double ans=0;
  for(int i=(n+1)/2;i<n+1;i++) ans+=dp[n][i];
  cout<<fixed<<setprecision(12)<<ans<<endl;
}

Measured memory_bytes: 70656
#include <cstdio>
#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

#define ALL(obj) (obj).begin(), (obj).end() 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ll ans=0, tsum=0;
    rep(i,n){
        if(a[i]==0){ 
            ans += tsum / 2;
            tsum=0;
        }else{
            tsum += a[i];
        }
    }
    cout << ans + (tsum / 2) << endl;
    return 0;
}

Measured memory_bytes: 1024
package main

import "fmt"

// 2019-03-31T23:08:18+0800
// 2019-03-31T23:14:29+0800
// 2019-03-31T23:22:56+0800
func main() {
	var N, M int
	fmt.Scanf("%d%d", &N, &M)
	//a := make([]int, M)
	//b := make([]int, M)
	var a, b int
	starts := make(map[int]bool, M)
	ends := make(map[int]bool, M)
	for i := 0; i < M; i++ {
		//fmt.Scanf("%d%d", &a[i], &b[i])
		fmt.Scanf("%d%d", &a, &b)
		if a == 1 {
			starts[b] = true
		} else if b == 1 {
			starts[a] = true
		} else if a == N {
			ends[b] = true
		} else if b == N {
			ends[a] = true
		}
	}

	for v := range starts {
		if ends[v] {
			fmt.Println("POSSIBLE")
			return
		}
	}
	fmt.Println("IMPOSSIBLE")
}

Measured memory_bytes: 11264
import sys
n, m, k = map(int, input().split())
prime_mod = 998244353

def prime_cycle_division(a, b):
  inverted = pow(b, prime_mod-2, prime_mod)
  return (a*inverted)%prime_mod

def gen_mod_combs(places):
  k = 0
  x = 1
  while True:
    yield x
    factor = prime_cycle_division(places-k, k+1)
    x = (x*factor)%prime_mod
    k += 1

def combos(j):
  ans = (m*next(gen))%prime_mod
  ans = (ans*pow(m-1, n-1-j, prime_mod))%prime_mod
  return ans

total = 0
gen = gen_mod_combs(n-1)
for j in range(k+1):
  total = (total + combos(j))%prime_mod
print(total)

Measured memory_bytes: 68416
n, y = map(int, input().split(" "))
c10000 = -1
c5000 = -1
c1000 = -1

for i in range(0, n + 1):
    for j in range(0, n + 1 - i):
        if 10000 * i + 5000 * j + 1000 * (n - i - j) == y:
            c10000 = i
            c5000 = j
            c1000 = n - i - j

print(str(c10000) + ' ' + str(c5000) + ' ' + str(c1000))

Measured memory_bytes: 9104
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
template <class T> vector<T> make_vec(size_t a, T val) {
    return vector<T>(a, val);
}
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
template <typename T> struct edge {
    int to;
    T cost;
    edge(int t, T c) : to(t), cost(c) {}
};
template <typename T> using WGraph = vector<vector<edge<T>>>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int H, W, M;
    cin >> H >> W >> M;
    vector<int> h(M), w(M);
    rep(i, M) { cin >> h[i] >> w[i]; }
    vector<int> counth(H);
    vector<pii> countw(W, MP(0, 0));
    rep(i, W) countw[i].second = i;
    map<pii, int> mp;
    rep(i, M) { mp[MP(h[i], w[i])]++; }
    rep(i, M) {
        counth[h[i] - 1]++;
        countw[w[i] - 1].first++;
    }
    sort(All(countw));
    reverse(All(countw));
    int mm = countw[0].first;
    set<int> mw;
    for(int i = 0; i < W; i++) {
        if(countw[i].first == countw[0].first)
            mw.insert(countw[i].second);
    }
    vector<int> plus(H);
    rep(i, M) {
        if(mw.count(w[i] - 1)) {
            plus[h[i] - 1]++;
        }
    }
    int res = 0;
    for(int i = 0; i < H; i++) {
        if(plus[i] == mw.size()) {
            res = max(res, counth[i] + mm - 1);
        } else {
            res = max(res, counth[i] + mm);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 43116
/*
digu_J - Digvijay Janartha
NIT Hamirpur - INDIA
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")

using namespace std;
using namespace __gnu_pbds;

template < typename T > using ordered_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#ifdef HOME
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    int len = comma - names;
    for (int i = 0; i < len; ++i) {
        cout << names[i];
    }
    cout <<  " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < ll, ll > pll;
typedef pair < int, int > pii;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef complex < double > com;

#define eb emplace_back
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define unique_sort(x) (sort(x.begin(), x.end()), x.resize(distance(x.begin(), unique(x.begin(), x.end()))))
#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

const ll LINF = LLONG_MAX, base = 1e9, MOD = 1e9 + 7, N = 1e5 + 5, M = 1e3 + 5, LG = 20;
const int INF = INT_MAX;
const db PI = acos(-1), EPS = 1 / db(1e6);
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());

void test() {
    int n;
    cin >> n;
    for (int i = 1; i <= 9; ++i) {
        if (n % i == 0 and n / i < 10) {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}

int main() {
    fast_io();
    #ifdef HOME
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    cout << fixed << setprecision(15);
    test();
    #ifdef HOME
        cout << "Time: " << (int)(clock() * 1000. / CLOCKS_PER_SEC) << "ms";
    #endif
    return 0;
}


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

int main( )
{
    int a, b, c = 0, p = 1, l;
    cin >> a >> b;
    while (b != 0) {
        c = p * (b % 10) + c;
        p *= 10;
        b /= 10;
    }
    b = a;
    while (b != 0) {
        c = p * (b % 10) + c;
        p *= 10;
        b /= 10;
    }
    int root = sqrt(c);
    if (root * root == c) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
    return 0;
}


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

using namespace std;
typedef long long ll;

int N;
ll A, B;
vector<ll> H;

ll calc_cnt(ll N, ll A, ll B, const vector<ll> &H, int t) {
  ll sub = A - B;
  ll ret = 0;
  for (int i = 0; i < N; i++) {
    if (H[i] - t * B > 0) {
      ret += (ll) ceil(1.0 * (H[i] - t * B) / sub);
    }
  }
  return ret;
}

int main() {
  cin >> N >> A >> B;
  H.resize(N);

  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }

  sort(H.begin(), H.end());
  int low = 0, high = (int) ceil(1.0 * H[N - 1] / B);
  while(low < high) {
    int mid = (low + high) / 2;
    if (calc_cnt(N, A, B, H, mid) <= mid) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  cout << high << endl;
  return 0;
}

Measured memory_bytes: 1024
//0071

#include<stdio.h>
#include<algorithm>
using namespace std;

const int N = 8;
char board[N][N+2];

void Fire(int i, int j)
{
	if(board[i][j] != '1')
		return;
	board[i][j] = '0';
	int d;
	for(d = max(j-3, 0); d < min(j+4, N); ++d)
	{
		Fire(i, d);
	}
	for(d = max(i-3, 0); d < min(i+4, N); ++d)
	{
		Fire(d, j);
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);
	int i;
	for(int caseNum = 1; caseNum <= n; ++caseNum)
	{
		for(i = 0; i < N; ++i)
		{
			scanf("%s", board[i]);
			if(board[i][0] == '\0')
				--i;
		}
		int x, y;
		scanf("%d %d", &x, &y);
		Fire(y-1, x-1);

		printf("Data %d:\n", caseNum);
		for(i = 0; i < N; ++i)
		{
			puts(board[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,0,n)
#define SORT(V) sort((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
using namespace std;

int main(){
  int A,B,C,ans=0;
  cin>>A>>B;
  C=B-A;
  ans=C*(C+1)/2;
  
  cout<<ans-B<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(c) (c).begin(),(c).end()

int main(){
  int N,K; cin>>N>>K;
  vector<pair<ll,ll>> S(N);
  vector<bool> var(N+10,false);
  ll t,d;
  for(int i=0;i<N;i++){
    cin>>t>>d;
    S[i]={d,t};
  }
  sort(all(S));
  multiset<ll> nu;
  ll ld=0,x=0;
  set<ll> ans;
  for(int i=0;i<N;i++){
    t=S[N-i-1].second;
    d=S[N-i-1].first;
    
    if(i<K){
      if(var[t]){
        nu.insert(d);
      }else{
        var[t]=true;
        x++;
      }
      ld+=d;
      if(i==K-1)
        ans.insert(ld+x*x);
    }else{
      if(nu.empty()) break;
      if(var[t]) continue;
      auto y=nu.begin();
      ld-=*y; ld+=d; x++;
      ans.insert(ld+x*x);
      y=nu.erase(y);
      var[t]=true; //デバッグ箇所
    }
  }
  auto aa=ans.rbegin();
  cout<<*aa<<endl;
}


Measured memory_bytes: 4224
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
class segtree{
public:
  ll Node;
  vector<ll> table;
  segtree(ll);
  ll ope(const ll,const ll);
  void update(ll index,const ll value){ // index is 0-indexed.
    index += Node; // query function
    table[index] += value;
    while(index > 0){
      index /= 2;
      table[index] = ope(table[2*index],table[2*index+1]);
    }
  }
  ll find(ll l, ll r);
};
ll segtree::find(ll l,ll r){ // l,r is 0-indexed.
  if(l == r) return table[r+Node];
  l += Node; r += Node;
  ll ans = 0;
  for(; l <= r;l >>=1, r >>=1){
    if(r == l){ans=ope(ans,table[l]); return ans;}
    if(r%2 == 0) ans=ope(ans,table[r]),--r;
    if(l%2) ans=ope(ans,table[l]),++l;
  }
  return ans;
}
segtree::segtree(ll Max_Node){  // initialize
  Node = 2;
  while(Node < Max_Node)
    Node *= 2;
  table.resize(2*Node);
  for(int i = Node;i < Node*2; i++)
    table[i] = INF; // initialize
  for(int i= Node-1; i > 0; i--)
    table[i] = ope(table[i*2],table[i*2+1]);
}

ll segtree::ope(const ll a,const ll b){
  return max(a,b);
}
int main(){
  ll n,t;cin>>n>>t;
  ll ma=-1;
  ll macnt=0;
  ll numm[n];
  segtree seg(n);
  for(int i=0;i<n;i++){
    cin>>numm[i];
    seg.update(i,numm[i]);
  }
  for(int i=0;i<n-1;i++){
    ll num=seg.find(i+1,n);
    if((num-numm[i])>ma){
      ma=(num-numm[i]);
      macnt=1;
    }else if((num-numm[i]==ma)){
      macnt++;
    }
  }
  cout<<macnt<<endl;
  return 0;
}

Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005,p=1000000007;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,m,a[N][N],ans;
vector<int> e[N];
unordered_set<int> g[N];
void build(int x,int fath,int *a,int val){
	a[x]=val;
	for (auto y : e[x])
	if (y!=fath) build(y,x,a,val);
}
bool chk(int x,int y,int z){
	return a[y][x]!=a[y][z];
}
void add(int u,int v){
	if (u==v) return;
	for (auto z : g[u])
	if (chk(u,z,v)) {add(z,v);return;}
	for (auto z : g[v])
	if (chk(u,z,v)) {add(z,u);return;}
	
	
	g[u].insert(v);
	g[v].insert(u);
	vector<int> f;
	f.clear();
	for (auto z : g[u])
	if ((z!=v)&&chk(u,v,z)) f.push_back(z);
	for (auto z : f)
	if (g[u].count(z)) {
		g[u].erase(z);
		g[z].erase(u);
		add(v,z);
	}
	f.clear();
	for (auto z : g[v])
	if ((z!=u)&&chk(v,u,z)) f.push_back(z);
	for (auto z : f)
	if (g[v].count(z)) {
		g[v].erase(z);
		g[z].erase(v);
		add(u,z);
	}
}
int work(int x,int fr){
	int t=1;
	for (auto y : g[x])
	if (chk(fr,x,y)) t+=work(y,x);
	return t;
}
int main(){
//	freopen("puzzle.in","r",stdin);
//	freopen("puzzle.out","w",stdout);
	n=read();m=read();
	for (int i=1;i<n;i++){
		int u=read(),v=read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for (int i=1;i<=n;i++)
	for (auto y : e[i]) build(y,i,a[i],y);
	for (int i=1;i<=m;i++){
		int u=read(),v=read();
		add(u,v);
	}
	for (int i=1;i<=n;i++)
	ans+=work(i,0)-1;
	printf("%d\n",ans/2);
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
using namespace std;
int mod = 1e9 + 7;

int dp[101][4][4][4];
int main() {
  int n;
  cin >> n;

  dp[0][3][3][3] = 1;
  for (int len = 0; len < n; ++len) {
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        for (int k = 0; k < 4; ++k) {
          if (dp[len][i][j][k] == 0) continue;

          for (int a = 0; a < 4; ++a) {
            if (a == 2 && i == 1 & j == 0) continue;
            if (a == 1 && i == 2 & j == 0) continue;
            if (a == 1 && i == 0 & j == 2) continue;
            if (a == 1 && i == 2 & k == 0) continue;
            if (a == 1 && j == 2 & k == 0) continue;

            dp[len + 1][a][i][j] += dp[len][i][j][k];
            dp[len + 1][a][i][j] %= mod;
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
        ans += dp[n][i][j][k];
        ans %= mod;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let xs = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun x -> x in
  let count = Array.make m 0 in
  let pairs = Array.make m 0 in
  begin
    let elt = Array.make 100001 false in
    Array.iter (fun x ->
      (if elt.(x) then pairs.(x mod m) <- 1 + pairs.(x mod m));
      elt.(x) <- not elt.(x);
      count.(x mod m) <- 1 + count.(x mod m)) xs
  end;
  Printf.printf "%d\n" @@
  Array.fold_left ( + ) 0 @@ 
  Array.init m @@ fun i ->
    if m - i < i then 0
    else if i = 0 || m - i = i then count.(i) / 2
    else begin
      let x = min count.(i) count.(m - i) in
      x
      + min (count.(i) - x) (2 * pairs.(i)) / 2
      + min (count.(m - i) - x) (2 * pairs.(m - i)) / 2
    end


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

int main(){
    string A,B,C;
    cin>>A>>B>>C;
    if(A.at(A.size()-1)==B.at(0)&&B.at(B.size()-1)==C.at(0)){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
#define MOD int(1e9+7)

int main()
{
    string S;
    vector<vector<long long>> mod(2, vector<long long>(13, 0));
    cin >> S;

    if (S[S.size() - 1] == '?')
    {
        for (long long j = 0; j < 10; j++)
            mod[(S.size() - 1) % 2][j] = 1;
    }
    else
        mod[(S.size() - 1) % 2][(int)(S[S.size() - 1]) - (int)('0')] = 1;

    long long ketamod = 1;
    if (S.size() >= 2)
    {
        for (long long i = S.size() - 2; i >= 0; i--)
        {
            ketamod = (ketamod * 10) % 13;
            if (S[i] == '?')
            {
                for (long long j = 0; j < 13; j++)
                    mod[i % 2][j] = 0;

                for (long long j = 0; j < 10; j++)
                    for (long long k = 0; k < 13; k++)
                        mod[i % 2][(k + j * ketamod) % 13] += mod[(i + 1) % 2][k];
            }
            else
            {
                for (long long k = 0; k < 13; k++)
                    mod[i % 2][(k + ((int)(S[i]) - (int)('0')) * ketamod) % 13] = mod[(i + 1) % 2][k];
            }

            for (long long j = 0; j < 13; j++)
                mod[i % 2][j] %= MOD;
        }
    }

    cout << mod[0][5] << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main(){
    char a;
    cin>>a;
    int ascii=a-'a';
    if(ascii>=0){
        cout<<'a';
    }else{
        cout<<'A';
    }

    return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pie 3.142857143
#define ll long long int
#define fr(i,a,n) for(ll i=a;i<n;i++)
#define vi vector<int>
#define vlli vector<ll>
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fv(i,a) for(auto i:a)
#define sz(a) int((a).size())
#define all(c) (c).begin(),(c).end()
#define frv(i,c) for(auto i = c.begin(); i != c.end(); i++)

void solve()
{
	ll x;
	fr(i, 0, 5)
	{
		cin >> x;
		if (x == 0)
			cout << i + 1 << endl;
	}

}


int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen ("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	//cin>>t;
	t = 1;
	while (t--)
	{
		solve();
	}


	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define adj_list vector<vi>
#define endl "\n"
#define INF_INT 2e9
#define INF_LL 2e18
#define matmax 25
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define pl pair<ll, ll>
#define pll pair<ll, pair<ll, ll> >
#define vi vector<int>
#define vl vector<ll>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long int ll;

int lsone(int n)
{
	return (n&-n);
}

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

ll n, w, weights[110], val[110];
ll dp[110000];

int main()
{
	fastio;		
	cin>>n>>w;
	ll tot = 0;
	for (int i = 1; i <= n; i++)
	{
		cin>>weights[i]>>val[i];
		tot += val[i];
	}

	for (int i = 0; i <= 1e5; i++)
		dp[i] = 1e18;

	dp[0] = 0;

	for (int i = 1; i <= n; i++)
	{
		for (int j = tot-val[i]; j >= 0; j--)
		{
			dp[j+val[i]] = min(dp[j+val[i]], dp[j]+weights[i]);
		}
	}

	ll ans = 0;

	for (int i = 1; i <= tot; i++)
	{
		if (dp[i] <= w)
			ans = i;
	}

	cout<<ans<<endl;

	return 0;
}


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

int main(){
	string s, t;
	cin >> s >> t;
	for (int i = 0; i < s.size(); i++){
		string u;
		u = u + s.at(s.size()-1);
		for (int j = 0; j < s.size()-1; j++)
			u = u + s.at(j);
		//cout << u << endl;
		if (u == t){
			cout << "Yes" << endl;
			return 0;
		}
		s = u;
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
t_list = [0]
x_list = [0]
y_list = [0]
for _ in range(n):
    data = input().split(' ')
    t_list.append(int(data[0]))
    x_list.append(int(data[1]))
    y_list.append(int(data[2]))
for i in range(n):
    t_diff = t_list[i + 1] - t_list[i]
    x_diff = abs(x_list[i + 1] - x_list[i])
    y_diff = abs(y_list[i + 1] - y_list[i])
    manhattan_dist = x_diff + y_diff
    if t_diff < manhattan_dist or (manhattan_dist - t_diff) % 2 == 1:
        print('No')
        exit(0)
print('Yes')

Measured memory_bytes: 11808
N=int(input())

if N==10000:
    print(0)
elif N>9000:
    print(10000-N)
elif N>8000:
    print(9000-N)
elif N>7000:
    print(8000-N)
elif N>6000:
    print(7000-N)
elif N>5000:
    print(6000-N)
elif N>4000:
    print(5000-N)
elif N>3000:
    print(4000-N)
elif N>2000:
    print(3000-N)
elif N>1000:
    print(2000-N)
else:
    print(1000-N)

Measured memory_bytes: 9192
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

vector<ll> a,p;

ll rec(int n,ll x){
    if(n == 0){
        if(x <= 0) return 0;
        else return 1;
    }else if(x <= 1 + a[n-1]){
        return rec(n-1,x-1);
    }else {
        return p[n-1] + 1 + rec(n-1,x-2-a[n-1]);
    }
}

int main(){
    int n;
    ll x;
    cin >> n >> x;
    a.resize(n+1);
    p.resize(n+1);
    a[0] = 1;
    p[0] = 1;
    reps(i,1,n+1){
        a[i] = 2*a[i-1] + 3;
        p[i] = 2*p[i-1] + 1;
    }

    cout << rec(n,x) << endl;
    return 0;
}


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

using namespace std;


int main(){
  int N;
  cin >> N;
  long long ans=0;
  long long minval=1e10;
  int coef = 0;
  for(int i=0;i<N;i++){
    long long tmp;
    cin >> tmp;
    coef = tmp<0 ? 2-coef: coef;
    tmp = abs(tmp);
    minval = min(minval, tmp);
    ans += tmp;
  }

  cout << ans - coef*minval;
  return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

/**
 * http://abc075.contest.atcoder.jp/tasks/abc075_a
 */
public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		sc.close();
		
		int ans = 0;
		if(a==b){
			ans = c;
		}else if(a==c){
			ans = b;
		}else{
			ans = a;
		}
		
		System.out.println(ans);

	}

}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;


int main() {
    

    ll n;
    cin >> n;
    vector <ll> x;
    for (ll i=0;i<n;i++){
        ll k;
        cin >> k;
        x.push_back(k);
    }
    ll ans = mop;
    for(ll i=1;i<=100;i++){
        ll tmp = 0;
        for(ll j=0;j<n;j++){
            tmp += (x[j] - i) * (x[j] - i);
        }
//        cout << i << " " << tmp << endl;
        if(tmp < ans){
            ans = tmp;

        }
    }
    cout << ans << endl;


}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int c = stdIn.nextInt();

		if (a < b && b < c) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		
	}

}



Measured memory_bytes: 26292
n, m, l = map(int, input().split())
result = [[0 for _ in range(l)] for _ in range(n)]

matrixA = [list(map(int, input().split())) for _ in range(n)]
matrixB = [list(map(int, input().split())) for _ in range(m)]

for i in range(n):
    for j in range(l):
        for k in range(m):
            result[i][j] += matrixA[i][k] * matrixB[k][j]

for r in result:
    for i, num in enumerate(r):
        print(num, end='')
        if i != l-1:
            print(end=' ')
    print()


Measured memory_bytes: 6968
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////

struct S{
  int num;
  int x;
  int y;
};

int main(){
  int h,w,n;
  C3(h,w,n);
  
  int f[h][w] = {};
  pair<int,int> g[n+1];
  pair<int,int> s[n+1];
  rep(i,0,h){
    rep(j,0,w){
      char c;
      cin >> c;
      if(c == 'X'){
        f[i][j] = -1;
      }
      else if(c == '.'){
        f[i][j] = 0;
      }
      else if(c == 'S'){
        pair<int,int> tt = {j,i};
        s[1] = tt;
      }
      else{
        int t = c - '0';
        f[i][j] = t;
        pair<int,int> tt = {j,i};
        g[t] = tt;
        
        if(t < n){
          s[t+1] = tt;
        }

      }
    }
  }

  int ans = 0;
  rep(i,1,n+1){
    int sx = s[i].first;
    int sy = s[i].second;
    int gx = g[i].first;
    int gy = g[i].second;
    //printf("sx:%d sy:%d gx:%d gy:%d\n",sx,sy,gx,gy);
    queue<struct S> q;
    struct S tmp = {0,sx,sy};
    q.push(tmp);
    
    int fNum[h][w];
    rep(i,0,h)
      rep(j,0,w)
      fNum[i][j] = 0xFFFFFFF;
    

    while(!q.empty()){
      struct S s = q.front();
      //printf("i:%d n:%d x:%d y:%d\n",i,s.num,s.x,s.y);
      q.pop();
      if(f[s.y][s.x] == -1){
        continue;
      }
      if(s.num >= fNum[s.y][s.x] && s.num != 0)
        continue;

      fNum[s.y][s.x] = s.num;
      if(s.y == gy && s.x == gx)
        continue;

      else{
        if(s.y > 0){
          if(f[s.y-1][s.x] != -1&& fNum[s.y-1][s.x] > s.num+1){
            struct S t = {s.num+1,s.x,s.y-1};
            q.push(t);
          }
        }
        if(s.x + 1 <= w - 1 ){
          if(f[s.y][s.x+1] != -1 && fNum[s.y][s.x+1] > s.num+1){
            struct S r = {s.num+1,s.x+1,s.y};
            q.push(r);
          }
        }
        if(s.x > 0){
          if(f[s.y][s.x-1] != -1 && fNum[s.y][s.x-1] > s.num+1){
            struct S l = {s.num+1,s.x-1,s.y};
            q.push(l);
          }
        }
        if(s.y + 1 <= h -1 ){
          if(f[s.y+1][s.x] != -1 && fNum[s.y+1][s.x] > s.num+1){
            struct S b = {s.num+1,s.x,s.y+1};     
            q.push(b);
          }
        }
      }
    }

    ans += fNum[gy][gx];
  }

  P(ans);

  ret 0;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

int dfs(VVI& G, int u, int p, VI& xs){
  for(int to: G[u]){
	if(xs[u] <= xs[to] || to == p) continue;
	if(!dfs(G, to, u, xs))
	  return 1;
  }
  return 0;
}

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

  int N;
  cin >> N;
  VI xs(N);
  REP(i,N) cin >> xs[i];
  VVI G(N);
  REP(i,N-1){
	int a, b;
	cin >> a >> b;
	--a;
	--b;
	G[a].PB(b);
	G[b].PB(a);
  }

  VI ans;
  REP(i,N){
	if(dfs(G, i, -1, xs))
	  ans.PB(i);
  }
  REP(i,SZ(ans))
	cout << (i?" ":"") << ans[i]+1;
  cout << endl;

  return 0;
}


Measured memory_bytes: 512
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

ll dp[11][210000];
const int INF=1e9;

int main() {
  ll d,g;
  cin>>d>>g;
  g/=100;
  
  vector<int> P(d+1),C(d+1);
  int x;
  rep(i,d){
    cin>>P[i+1]>>x;
    C[i+1]=x/100;
  }
  
  rep(i,11){
    rep(j,210000) dp[i][j]=INF;
  }
  dp[0][0]=0;
  
  for(int i=1;i<=d;i++){
    for(int j=0;j<=g+20000;j++){
      for(int k=0;k<P[i];k++){
        if(j-k*i<0) continue;
        dp[i][j]=min(dp[i][j],dp[i-1][j-k*i]+k);
      }
      if(j-P[i]*i-C[i]<0) continue;
      dp[i][j]=min(dp[i][j],dp[i-1][j-P[i]*i-C[i]]+P[i]);
    }
  }
  ll ans=INF;
  for(int i=g;i<=g+20000;i++){
    ans=min(ans,dp[d][i]);
  }
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 21672
#include <iostream>
#include <vector>
using namespace std;
int main(){
	bool ms[300001];
	for(int i=2;i<=300000;i++){
		if(i%7==1 || i%7==6){
			ms[i]=true;
		}else{
			ms[i]=false;
		}
	}
	for(int i=1;i<=42857;i++){
		if(ms[7*i-1]==true){
			for(int j=(7*i-1)*2;j<=300000;j+=7*i-1){
				ms[j]=false;
			}
		}
		if(ms[7*i+1]==true){
			for(int j=(7*i+1)*2;j<=300000;j+=7*i+1){
				ms[j]=false;
			}
		}
	}
	int n;
	while(cin>>n){
		if(n==1) break;
		vector<int> com;
		for(int k=1;k<=42857;k++){
			if(ms[7*k-1]==true){
				if(n%(7*k-1)==0){
					com.push_back(7*k-1);
				}
			}
			if(ms[7*k+1]==true){
				if(n%(7*k+1)==0){
					com.push_back(7*k+1);
				}
			}
		}
		cout<<n<<":";
		for(int p=0;p<com.size();p++){
			cout<<" "<<com[p];
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1508
#![allow(unused_macros)]

// cf. [Rustで競技プログラミングの入力をスッキリ記述するマクロ - Qiita](https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8)
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        N: usize,
        T: usize,
        AB: [(usize, usize); N],
    }
    let mut AB = AB;
    use std::cmp::Ordering;
    AB.sort_by(|a, b| match a.0.cmp(&b.0) {
        Ordering::Equal => a.1.cmp(&b.1),
        x => x,
    });

    use std::cmp::max;
    let mut dp = vec![vec![0; T + 1]; N + 1];
    for i in 0..AB.len() {
        for j in 0..T {
            if j >= AB[i].0 {
                dp[i + 1][j] = max(dp[i][j - AB[i].0] + AB[i].1, dp[i][j]);
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }

    let mut ans = AB[0].1;
    for i in 1..N {
        ans = max(dp[i][T - 1] + AB[i].1, ans);
    }
    println!("{}", ans);
}


Measured memory_bytes: 90364
#include <iostream>
#include <iomanip>
#include <string>
#include <unordered_map>
#include <cmath>
#include <algorithm>

typedef long long ll;
typedef long double ld;

using namespace std;
int main()
{
  ll n, p[200010], minp, cnt;
  cin >> n;
  for (ll i = 0; i < n; ++i)
  {
    cin >> p[i];
  }

  minp = p[0];
  cnt = 1;
  for (ll i = 1; i < n; ++i)
  {
    if (p[i] <= minp)
    {
      minp = p[i];
      ++cnt;
    }
  }

  cout << cnt << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define M 100000007
typedef pair<int,int> P;
int main(void){
	int n,m,k;
	while(1){
		cin>>n>>m;
		if(n==0)break;
		vector<P> cost[m+1],time[m+1];
		for(int i=0;i<n;i++){
			int a,b,c,t;
			cin>>a>>b>>c>>t;
			cost[a].push_back(P(b,c)); cost[b].push_back(P(a,c));
			time[a].push_back(P(b,t)); time[b].push_back(P(a,t));
		}
		cin>>k;
		for(int i=0;i<k;i++){
			int s,g,f;
			int leng[m+1];
			priority_queue<P,vector<P>,greater<P> > que;
			fill(leng,leng+m+1,M);
			cin>>s>>g>>f;
			leng[s]=0;
			que.push(P(0,s));
			if(f==0){
				while(!que.empty()){
					P p=que.top(); que.pop();
					int v=p.second;
					if(leng[v]<p.first) continue;
					for(int j=0;j<cost[v].size();j++){
						P x=cost[v][j];
						if(leng[x.first]>leng[v]+x.second){
							leng[x.first]=leng[v]+x.second;
							que.push(P(leng[x.first],x.first));
						}
					}
				}
				cout<<leng[g]<<endl;
			}else{
				while(!que.empty()){
					P p=que.top(); que.pop();
					int v=p.second;
					if(leng[v]<p.first) continue;
					for(int j=0;j<time[v].size();j++){
						P x=time[v][j];
						if(leng[x.first]>leng[v]+x.second){
							leng[x.first]=leng[v]+x.second;
							que.push(P(leng[x.first],x.first));
						}
					}
				}
				cout<<leng[g]<<endl;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3168
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
using namespace std;
typedef long long ll;

int main(){
  ll a,b;
  cin >> a >> b;
  cout << (a+b+1)/2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(long long i=a; i<b; i+=1)
#define repr(i,a,b) for(long long i=a; i<=b; i+=1)
#define vec vector<ll>
#define map map<string,int>
#define repa(p,A) for(auto p:A)
#define pb push_back
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
 
using namespace std;
int main() {
  ll N,S;
  cin>>N;
  S=(N*(N+1))/2;
  rep(i,3,N+1) {
    if(i%3==0 || i%5==0)
      S-=i;
  }
  cout<<S<<endl;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define N 1000123
#define vi vector<int>
#define vll vector<ll>
#define vpll vector<pll>
#define pb emplace_back
#define fs first
#define sc second
#define sz(x) ((int)((x).size()))
#define oo 1000000123
#define mod 1000000007LL
#define M 10000123
 
using namespace std;

ll v[N], ans;
priority_queue<pll> pq;
int n;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> v[i];
    }

    sort(v, v + n, greater<ll>());

    ans = v[0];
    pq.push(pll(min(v[0], v[1]), max(v[0], v[1])));
    pq.push(pll(min(v[0], v[1]), max(v[0], v[1])));
    
    pll topo;
    for(int i = 2; i < n; ++i) {
        topo = pq.top();
        pq.pop();
        
        ans += topo.fs;
        pq.push(pll(min(topo.fs, v[i]), max(topo.fs, v[i])));
        pq.push(pll(min(topo.sc, v[i]), max(topo.sc, v[i])));
    }

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


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

using namespace std;

int main(){
	int  N,val,kk,mm;
	vector<int> first;
	vector<int> sec;
	int maxi=0;
	cin>>N;

	for(int i=0;i<(N);i++){
		cin>>val;
		first.push_back(val);
	}

	for(int j=0;j<(N);j++){
		cin>>val;
		sec.push_back(val);
	}
	kk=0;
	for(int k=0;k<N;k++){
		kk=kk+first[k];
		mm=0;

		for(int m=k;m<N;m++){
			mm=mm+sec[m];

		}

		maxi=max(maxi,kk+mm);
	}
	cout<<maxi<<endl;


	return 0;
}

Measured memory_bytes: 256