akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl
#define printD(a) cout << setprecision(15) << (a) << endl;
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<auto>& a,int n);
double PI = 3.14159265358979;
int n;

int ld_(string s1,string s2){
    if(s1.size() == 0) return s2.size();
    if(s2.size() == 0) return s1.size();
    if(s1[0] == s2[0]) return ld_(s1.substr(1),s2.substr(1));
    int l1 = ld_(s1,s2.substr(1));
    int l2 = ld_(s1.substr(1),s2);
    int l3 = ld_(s1.substr(1),s2.substr(1));
    return 1 + min({l1,l2,l3});
}

int ld(string s1,string s2){
    if(s1.size() == 0) return s2.size();
    if(s2.size() == 0) return s1.size();
    int n = s1.size()+1;
    int m = s2.size()+1;
    twovec(dp,n,m);
    REP(i,n){
        dp[i][0] = i;
    }
    REP(i,m){
        dp[0][i] = i;
    }
    FOR(i,1,n){
        FOR(j,1,m){
            int cost = 1;
            if(s1[i-1] == s2[j-1]) cost = 0;
            dp[i][j] = min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost});
        }
    }
    /*
    REP(i,n){
        Debug(dp[i]);
    }
    */
    return dp[n-1][m-1];

}



signed main(){
    string s1,s2;
    cin >> s1 >> s2;
    print(ld(s1,s2));

    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}

//key以上の初めてのitr
int nibul(auto a,auto b){return lower_bound(All(a),b) - a.begin();}
//key以下の最後のitr
int nibuu(auto a,auto b){return upper_bound(All(a),b) - a.begin()-1;}

void input(vector<auto>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}



Measured memory_bytes: 10872
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int n,a; cin >> n >> a;
    if (n % 500 <= a)
    {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.range;
import std.stdio;
import std.string;

void main()
{
	auto n = readln.strip.to!int;
	auto s = readln.strip.map!( to!dchar ).array;
	auto result = 0;
	
	for( int index = 1; index < s.length - 1; index++ )
	{
		auto x = sort( s[ 0 .. index ].dup ).uniq;
		auto y = s[ index .. $ ];
		auto max = 0;
		
		if( x.walkLength < result ) continue;
		if( y.length < result ) break;
		
		foreach( xc; x )
		{
			if( y.find( xc ) != null ) max++;
		}
		
		if( result < max ) result = max;
	}
	
	writeln( result );
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import collections


def solve(N: int, a):
    c = collections.Counter(a)
    z = 0
    for k, v in c.items():
        if v - k < 0:
            z += v
        else:
            z += v - k
    print(z)


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

if __name__ == '__main__':
    main()


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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

template <typename T>
struct Edge {
  int src, dst; T weight;

  Edge(int src, int dst, T weight) : src(src), dst(dst), weight(weight) { }

  bool operator < (const Edge<T> &e) const {
    return weight < e.weight;
  }
};

template <typename T>
struct Graph {
  int V;
  vector<Edge<T>> E;

  Graph(int V) : V(V) { }

  void add_edge(int src, int dst, T weight) {
    E.emplace_back(src, dst, weight);
  }
};

struct DisjointSet {
  vector<int> parent, rank;

  DisjointSet(int N) {
    parent.resize(N), rank.resize(N, 0);
    for (int i = 0; i < N; i++) parent[i] = i;
  }

  int find(int x) {
    if (parent[x] == x) {
      return x;
    } else {
      return parent[x] = find(parent[x]);
    }
  }

  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return ;
    if (rank[x] < rank[y]) {
      parent[x] = y;
    } else {
      parent[y] = x;
      if (rank[x] == rank[y]) rank[x]++;
    }
  }

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

template <typename T>
struct MinimumSpanningTree {
  Graph<T> g;
  vector<Edge<T>> mst;
  T mincost;

  MinimumSpanningTree(const Graph<T> &g) : g(g) { }

  T kruskal() {
    mincost = 0;
    sort(g.E.begin(), g.E.end());

    DisjointSet uf(g.V);

    for (int i = 0, edge_count = g.V - 1; edge_count; i++) {
      assert(i < (int)g.E.size());
      Edge<T> e = g.E[i];
      if (!uf.same(e.src, e.dst)) {
	uf.unite(e.src, e.dst);
	mst.emplace_back(e);
	mincost += e.weight;
	edge_count--;
      }
    }
    return mincost;
  }
};

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int V, E; cin >> V >> E;
  Graph<int> g(V);
  REP(_, E) {
    int s, t, w; cin >> s >> t >> w;
    g.add_edge(s, t, w);
  }
  MinimumSpanningTree<int> mst(g);
  cout << mst.kruskal() << endl;

  return 0;
}

Measured memory_bytes: 5652
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

void solve() {
  long N;
  cin >> N;
  vector<long> h(N);
  rep (i, N) cin >> h[i];

  long ans = 0;

  for (long i = 0; i < 110; i++) {
    bool flag = true;
    rep (i, N) {
      if (h[i]) {
        h[i]--;
        if (flag) {
          ans++;
          flag = false;
        }
      } else flag = true;
    }
  }

  cout << ans << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


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

using ll = long long;

#define N 100005

int n, x[N], l[N], L[N], R[N], id[N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d %d", &x[i], &l[i]);
		L[i] = x[i] - l[i];
		R[i] = x[i] + l[i];
		id[i] = i;
	}
	sort(id+1, id+n+1, [](int x, int y) {return R[x] < R[y];});
	int prv = -1e9-100, ans = 0;
	for (int ii = 1; ii <= n; ii ++) {
		int i = id[ii];
		int cur = L[i];
		if (prv <= cur) {
			prv = R[i];
			ans ++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2176
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#define int long long
#define mod(int)(1000000007)
using namespace std;
int d[2134][2134];
void warshall_floyd(int V) {
	for (int h = 0; h < V; h++) {
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
				d[i][j] = min(d[i][j], d[i][h] + d[h][j]);
			}
		}
	}
}
signed main() {
	int n, m, a, b, ans = 0; cin >> n >> m;
	for (int h = 0; h <= 9; h++) {
		for (int i = 0; i <= 9; i++) {
			cin >> a;
			d[h][i] = a;
		}
	}
	warshall_floyd(10);
	for (int h = 0; h < n; h++) {
		for (int h = 0; h < m; h++) {
			cin >> b;
			if (b != -1) {
				ans += d[b][1];
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

signed main(){
  fastio
  ll n,k;cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++)  cin>>a[i],a[i]--;
  int visit[n]={0};
  visit[0]=1;
  int i=0;
  while(k){
    if(!visit[a[i]]){
      visit[a[i]]=visit[i]+1;
      i=a[i];
      k--;
    }else{
      int new_depth=visit[i]+1;
      int cycle=abs(visit[a[i]]-new_depth);
      k%=cycle;
      while(k){
        i=a[i];
        k--;
      }
    }
  }
  cout<<i+1<<"\n";
  return 0;
}

Measured memory_bytes: 5220
#include <cstdio>
int N,T,A,X;
int main()
{
  scanf ("%d%d%d",&N,&T,&A);
  int res=0; 
  int cc=1<<30;
  for (int i=1;i<=N;i++)
  {
    scanf ("%d",&X);
    int d=(T*1000-X*6)-A*1000;
    if (d<0)d=-d;
    if (cc>d)cc=d,res=i;
  }
  printf ("%d\n",res);
}

Measured memory_bytes: 128
for i in range(10000):
  x = input().split()
  h = int(x[0])
  w = int(x[1])
  if h == 0 and w ==0:
    break
  for i in range(w):
    print("#",end="")
  print()  
  for i in range(h-2):
    print("#",end="")
    for i in range(w-2):
      print(".",end="")
    print("#",end="")
    print()
  for i in range(w):
    print("#",end="")
  print()
  print()  


Measured memory_bytes: 7000
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cassert>
using namespace std;

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

	int h, w;
	cin >> h >> w;
	vector<string> grid(h);
	for (string& s : grid) cin >> s;
	
	bool ans = true;
	for (int i = 0; i < h && ans; i++) {
		for (int j = 0; j < w && ans; j++) {
			if (grid[i][j] == '.') continue;
			if (i > 0 && grid[i-1][j] == '#') continue;
			if (i < h-1 && grid[i+1][j] == '#') continue;
			if (j > 0 && grid[i][j-1] == '#') continue;
			if (j < w-1 && grid[i][j+1] == '#') continue;
			ans = false;
		}
	}
	
	cout << (ans? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

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

class CommonIO {
public:
    CommonIO() {
        std::cin.tie(0);
        std::ios::sync_with_stdio(false);
    }
    ~CommonIO() {}

    template <class T>
    void scan(T &v) {
        std::cin >> v;
    }
    template <class T, class... Rest>
    void scan(T &v, Rest&... rest) {
        scan(v);
        scan(rest...);
    }

    template <class T>
    void print(T v) {
        std::cout << v;
    }
    template <class T>
    void print(std::vector<T> &v) {
        if (v.size() == 0) return;
        print(*v.begin());
        for (auto it = ++v.begin(); it != v.end(); ++it) {
            print(' ');
            print(*it);
        }
    }
    template <class T>
    void print(std::vector< std::vector<T> > &grid) {
        if (grid.size() == 0) return;
        print(*grid.begin());
        for (auto it = ++grid.begin(); it != grid.end(); ++it) {
            print('\n');
            print(*it);
        }
    }
    template <class T, class... Rest>
    void print(T v, Rest... rest) {
        print(v);
        print(' ');
        print(rest...);
    }

    template <class T>
    void printl(T v) {
        print(v);
        std::cout << '\n';
    }
    template <class T, class... Rest>
    void printl(T v, Rest... rest) {
        print(v);
        print(' ');
        printl(rest...);
    }
} io;


uint selectionSort(vector<int> &a, int N) {
  uint count = 0;
  int minj;
  REP(i, N) {
    minj = i;
    FOR(j, i, N) {
      if (a[j] < a[minj]) minj = j;
    }
    if (i != minj) {
      swap(a[i], a[minj]);
      ++count;
    }
  }
  
  return count;
}

int main() {
  int n; io.scan(n);
  vector<int> a(n);
  REP(i, n) io.scan(a[i]);
  
  uint count = selectionSort(a, n);
  io.printl(a);
  io.printl(count);
  return 0;
}



Measured memory_bytes: 3152
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < n; ++i)
#define FOR(i, b, n) for (ll i = b; i < n; ++i)

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

ll MAX = 1000000000;

int main(){
  // int 3E4  long 2E9  ll 9E18
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll N;
  cin >> N;

  P lb, lt, rb, rt;
  ll mind(MAX), maxd(0), xd(-MAX), yd(-MAX);
  

  ll x, y;
  REP(i, N) {
    cin >> x >> y;
    P p(x, y);
    if (x + y < mind) {
      lb = p;
      mind = x + y;
    }
    if (x + y > maxd) {
      rt = p;
      maxd = x + y;
    }
    if (x - y > xd) {
      rb = p;
      xd = x - y;
    }
    if (y - x > yd) {
      lt = p;
      yd = y - x;
    }
  }
  ll ans = max(abs(lt.first - rb.first) + abs(lt.second - rb.second),
	       abs(rt.first - lb.first) + abs(rt.second - lb.second));
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3648
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Aizu
{
    class Program
    {
        static void Main(string[] args)
        {
            var firstLine = Console.ReadLine().Split(' ').Select(value => int.Parse(value)).ToArray();
            var n = firstLine[0];
            var w = firstLine[1];
            var goods = new List<int[]>();

            for(var i = 0; i < n; i++)
            {
                goods.Add(Console.ReadLine().Split(' ').Select(value => int.Parse(value)).ToArray());
            }

            var knapsack = new int[n + 1, w + 1];

            for (var i = 0; i <= n; i++)
            {
                for(var j = 0; j <= w; j++)
                {
                    if(i == 0 || j == 0)
                    {
                        knapsack[i, j] = 0;
                    }
                    else
                    {
                        knapsack[i, j] = int.MaxValue;
                    }
                }
            }

            for (var i = 1; i <= n; i++)
            {
                for (var j = 1; j <= w; j++)
                {
                    if (j - goods[i - 1][1] >= 0)
                    {
                        knapsack[i, j] = Math.Max(knapsack[i - 1, j], knapsack[i - 1, j - goods[i - 1][1]] + goods[i - 1][0]);
                    }
                    else
                    {
                        knapsack[i, j] = knapsack[i - 1, j];
                    }
                }
            }

            Console.WriteLine(knapsack[n, w]);
        }
    }
}



Measured memory_bytes: 21888
def main():
    bingo = []
    for i in range(3):
        bingo.append(list(map(int, input().split())))

    n = int(input())
    exsit = [int(input()) for i in range(n)]
    for e in exsit:
        for b in bingo:
            if b.count(e) == 1:
                b[b.index(e)] = 0
    naname = [0, 0]
    for i in range(len(bingo)):
        if bingo[i].count(0) == 3:
            print('Yes')
            exit()
        elif [bingo[j][i] for j in range(3)].count(0) == 3:
            print('Yes')
            exit()
        naname[0] += 1 if bingo[i][i] == 0 else 0
        naname[1] += 1 if bingo[i][2 - i] == 0 else 0

    if naname[0] == 3 or naname[1] == 3:
        print('Yes')
    else:
        print('No')



if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner cin = new Scanner(System.in);
		
		String S = cin.next();
		
		int N = S.length();
		
		int n1 = (N-1)/2-1;
		int n2 = (N+3)/2-1;
		
		boolean flag = true;
		for(int i = 0;i<=n1;i++) {
			if(S.charAt(i)!=S.charAt(n1-i)) {
				flag = false;
				break;
			}
		}
		
		for(int j = n2;j<N;j++) {
			if(S.charAt(j)!=S.charAt(N-1-j)) {
				flag = false;
				break;
			}
		}
		
		if(flag) System.out.println("Yes");
		else System.out.println("No");

	}

}


Measured memory_bytes: 21844
#define _CRT_SECURE_NO_WARNINGS // #pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <sstream>
#include <cmath>
#include <set>
#include <map>
using namespace std; 

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define len(x) ((int)(x).size())
#define tmax(a,b,c) max((a),max((b),(c)))
#define tmin(a,b,c) min((a),min((b),(c)))
#define debug(x) cerr << #x << " is " << x << endl;

typedef pair<int, int> Pii;
typedef vector<int> Vi;
typedef vector<vector<int> > VVi;
typedef long long ll;
const int inf = 2e9;
const ll ll_inf = 1e17;
const int mod = 1e9 + 7;
const long double eps = 1e-10;

int prime[250000];

int main()
{
	rep(i,2,501) {
		int j = i*2;
		while (j < 250000) {
			prime[j]++;
			j += i;
		}
	}
	prime[0]++;
	prime[1]++;

	while(1) {
		int n;
		cin >> n;
		if (!n) break;
		int cnt = 0;
		rep(i,n+1,n*2+1) if (!prime[i]) {
			//debug(i);
			cnt++;
		}
		cout << cnt << endl;
	}

	return 0;
}

Measured memory_bytes: 2136
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> A(H, vector<char>(W));
  queue<pair<int, int>> que;
  rep(i, H) { 
    rep(j, W) {
      cin >> A[i][j];
      if(A[i][j] == '#')
        que.push({i, j});
    }
  }
  int ans = 0;
  vector<vector<int>> num(H, vector<int>(W));
  while(!que.empty()) {
    int x, y;
    tie(x, y) = que.front();
    que.pop();
    int n = num[x][y];
    rep(i, 4) {
      if(x+dx[i] < 0 || x+dx[i] >= H || y+dy[i] < 0 || y+dy[i] >= W)
        continue;
      if(A[x+dx[i]][y+dy[i]] == '.') {
        A[x+dx[i]][y+dy[i]] = '#';
        num[x+dx[i]][y+dy[i]] = n+1;
        chmax(ans, n+1);
        que.push({x+dx[i], y+dy[i]});
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 13456
/* Hariom_Pandey
      16.11.2019  */
#include<bits/stdc++.h>
using namespace std;


int main()
{
    long long int n;
    cin>>n;
    string s;
    long long int f=0;
    cin>>s;
    sort(s.begin(), s.end());

    for(int i=0; i<n; i++)
    {
        if(s[i]!=s[i+1])
        {
            cout<<"No";
            f=1;
            break;
        }
        else
            i+=1;
    }
    if(f==0)
        cout<<"Yes"<<"\n";
   
}

Measured memory_bytes: 256
function frac(){
    readonly mul=100000
    readonly mullen=${#mul}
    local a=$1
    local b=$2
    local tmp=`printf "%0${mullen}d" $((a*mul/b))`
    local tmplen=${#tmp}
    local ilen=$((tmplen-(mullen-1)))
    local flen=$((mullen-1))
    echo ${tmp:0:$ilen}"."${tmp: -$flen}
}
read n
s=0
for i in `seq $n`
do
    read x u
    case $u in
        "JPY")
            s=$((s+x*10000));;
        "BTC")
            x=`echo $x | tr -d \. | sed -r "s/^0+//"`
            s=$((s+x*38))
    esac
done
frac $s 10000

Measured memory_bytes: 3704
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n, m = intin()
    alist = intina()
    alist.insert(0, 0)

    asumlist = []
    asum = 0
    for a in alist:
        asum += a
        asumlist.append(asum)

    asumlist = [asum % m for asum in asumlist]
    asumlist.sort()
    asumlist.append(None)

    ans = 0
    asum_now = None
    asum_count = 0
    for asum in asumlist:
        if asum == asum_now:
            asum_count += 1
        else:
            if asum_count >= 2:
                ans += combination(asum_count, 2)
            asum_now = asum
            asum_count = 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 16620
unittest
{
	assert( [ "5 3", "1 9", "1 7", "2 6", "2 5", "3 1" ].solve == 26 );
	assert( [ "7 4", "1 1", "2 1", "3 1", "4 6", "4 5", "4 5", "4 5" ].solve == 25 );
	assert( [ "6 5", "5 1000000000", "2 990000000", "3 980000000", "6 970000000", "6 960000000", "4 950000000" ].solve == 4900000016 );
}



import std.algorithm;
import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto k = 0L;
	input.front.formattedRead!"%s %s"( n, k );
	auto tds = new long[ 2 ][ n ];
	foreach( ref td; tds )
	{
		input.popFront;
		td = input.front.split.to!( long[] );
	}
	tds.multiSort!( ( a, b ) => b[ 1 ] < a[ 1 ], ( a, b ) => a[ 0 ] < b[ 0 ] );
	
	// おいしい順にk個食べたときの満足ポイントを計算
	auto m = 0L;
	auto tc = 0L;
	auto ts = new long[ 10L ^^ 5 ];
	foreach( td; tds[ 0 .. k ] )
	{
		tc += ( ts[ td[ 0 ] ] == 0 );
		ts[ td[ 0 ] ]++;
		m += td[ 1 ];
	}
	
	// ネタの種類が増えるように入れ替えたときの満足ポイントを計算
	auto ans = m + tc ^^ 2;
	auto p = k - 1;
	foreach( td; tds[ k .. $ ] )
	{
		if( 0 < ts[ td[ 0 ] ] ) continue;
		
		while( 0 <= p && ts[ tds[ p ][ 0 ] ] <= 1 ) p--;
		if( p <= 0 ) break;
		
		m -= tds[ p ][ 1 ] - td[ 1 ];
		tc++;
		ts[ tds[ p ][ 0 ] ]--;
		ts[ td[ 0 ] ]++;
		p--;
		ans = max( ans, m + tc ^^ 2 );
	}
	return ans;
}


Measured memory_bytes: 6300
import java.util.*;

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

  Scanner sc;
  int N;
  int M;
  int answer;
  int[] K;
  int[][] A;

  // 標準入力用のコンストラクタ
  public Main(Scanner sc) {
    this.sc = sc;
    N = sc.nextInt();   //調査人数
    M = sc.nextInt(); 	//食べ物の種類数
    K = new int[N]; 	//N人それぞれの好きな料理の個数
    A = new int[N][M];
    for (int i = 0; i < N; ++i){
        K[i] = sc.nextInt();
        for (int j = 0; j < K[i]; ++j){
            A[i][j] = sc.nextInt();
        }
    }
  }

  // 判定処理
  int solve() {
      int count = 0;
      int[] like = new int[M];   //各料理ごとに好きだと答えた人数を格納する配列
      for (int i = 0; i < N; ++i){
        for (int j = 0; j < K[i]; ++j){
            like[A[i][j] -1]++; //K[i]番目の料理が好き
        }
      }
      for (int i = 0; i < M; ++i){  //各料理の「好きだ」と解答した人数を調べる
        if (like[i] == N){  //その料理を全員が好きであればカウント
            ++count;
        }
      }
      
      answer = count;
      return answer;
  }

  // 回答の表示
  void show(int answer) {
        System.out.println(answer);
  }
    
}

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

int main(){
  string s;
  cin >> s;
  int x, y;
  cin >> x >> y;
  vector<int> vecx, vecy;
  bool X = true;
  int ls = s.length();
  int l = 0;
  rep(i, ls){
    if(s[i] == 'F'){
      l++;
    } else if(X) {
      vecx.push_back(l);
      l = 0;
      X = false;
    } else {
      vecy.push_back(l);
      l = 0;
      X = true;
    }
  }
  X? vecx.push_back(l) : vecy.push_back(l);
  int sx = vecx.size(), sy = vecy.size();
  vector<vector<bool>> dpx(sx+1, vector<bool>(2*ls+1, false));
  vector<vector<bool>> dpy(sy+1, vector<bool>(2*ls+1, false));
  dpy[0][ls] = true, dpx[1][ls+vecx[0]] = true;
  for(int i = 1; i < sx; i++){
    rep(j, 2*ls+1){
      if(dpx[i][j]){
        dpx[i+1][j+vecx[i]] = true;
        dpx[i+1][j-vecx[i]] = true;
      }
    }
  }
  rep(i, sy){
    rep(j, 2*ls+1){
      if(dpy[i][j]){
        dpy[i+1][j+vecy[i]] = true;
        dpy[i+1][j-vecy[i]] = true;
      }
    }
  }

  if(dpx[sx][x+ls] && dpy[sy][y+ls]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 16128
#include <stdio.h>
int main(void)
{
    int i,n,cnt = 0;
    scanf("%d",&n);
    int a[n];
    for(i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
        if(a[i] % 2 == 0 && a[i] % 3 != 0 && a[i] % 5 != 0)
            cnt++;
    }
    if(cnt == 0)
        printf("APPROVED");
    else
        printf("DENIED");
        
    return 0;
}


Measured memory_bytes: 128
a,b,c,d=map(int,input())
A,B,C,D=str(a),str(b),str(c),str(d)
if a+b+c+d==7:
    print(A+"+"+B+"+"+C+"+"+D+"=7")
elif a+b+c-d==7:
    print(A+"+"+B+"+"+C+"-"+D+"=7")
elif a+b-c+d==7:
    print(A+"+"+B+"-"+C+"+"+D+"=7")
elif a-b+c+d==7:
    print(A+"-"+B+"+"+C+"+"+D+"=7")
elif a+b-c-d==7:
    print(A+"+"+B+"-"+C+"-"+D+"=7")
elif a-b+c-d==7:
    print(A+"-"+B+"+"+C+"-"+D+"=7")
elif a-b-c+d==7:
    print(A+"-"+B+"-"+C+"+"+D+"=7")
else:
    print(A+"-"+B+"-"+C+"-"+D+"=7")

Measured memory_bytes: 62000
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;


typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

vector<char> moto {'7','5','3'};

bool is_contain(string s){
    bool b7 = false,b5 = false, b3 = false;
    REP(i,s.length()) {
        if (s[i] ==  '7') b7 = true;
        if (s[i] ==  '5') b5 = true;
        if (s[i] ==  '3') b3 = true;
    }
    return b7 and b5 and b3;
}


int dfs(const ll max, string now){
    if (now != "") if (stoll(now) > max) return 0;

    int tmp = 0;
    if (is_contain(now)) {
        tmp++;
    }
    for (char c : moto) tmp += dfs(max,now+c);
    return tmp;
}

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

    ll N;
    cin >> N;

    cout << dfs(N,"") << endl;

    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
using namespace std;
int main()
{
    int h, w;
    cin >> h >> w;
    char a[105][105], b[105][105];

    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
        {
            cin >> a[i][j];
        }
    }

    for(int i = 0; i < h + 2; i++)
    {
        for(int j = 0; j < w + 2; j++)
        {
            if(i > 0 || i < h + 1 || j > 0 || j < w + 1)
                b[i][j] = a[i - 1][j - 1];
            if(i == 0 || j == 0 || i == h + 1 || j == w + 1)
                b[i][j] = '#';
        }
    }

    for(int i = 0; i < h + 2; i++)
    {
        for(int j = 0; j < w + 2; j++)
        {
            cout << b[i][j];
        }
        cout << endl;
    }

    return 0;
}

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

using namespace std;
typedef long long int ll;

int main(){
    int N;
    cin >> N;
    vector<ll> a(N);
    ll sum = 0;

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

    ll res=10000000000LL,tmp=0;
    for (int i = 0; i < N;i++){
        tmp += a[i];
        if(i+1<N)
            res = min(res, abs(sum - 2 * tmp));
    }
    cout << res << endl;
}

Measured memory_bytes: 1792
eval"N,C,*H="+`dd`.split*?,;g,*q=->i{x,y=q[i,2];1.0*($*[x]-$*[y])/(H[y]-H[x])-H[x]-H[y]};N.times{|i|q.shift while q.size>1&&g[0]>-2*H[i];$*<<(i>0?$*[q[0]]+C+(H[q[0]]-H[i])**2:0);q<<i;q.delete_at(-2)while q.size>2&&g[-2]>g[-3];};p$*[-1]

Measured memory_bytes: 56024
#include<stdio.h>

int main(void) {
	int K, N;
	scanf("%d%d", &K, &N);
	int A[N], B[N], i;
	for (i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	B[0] = K - A[N - 1] + A[0];
	for (i = 1; i < N; i++) {
		B[i] = A[i] - A[i - 1];
	}
	int MAX = B[0];
	for (i = 1; i < N; i++) {
		if (MAX < B[i]) MAX = B[i];
	}
	printf("%d", K - MAX);

	return 0;
}

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

int main() {
	string N;
  	cin>>N;
  	if(N[0]==N[1]&&N[1]==N[2]){
      cout<<"Yes"<<endl;
    }
  	else if(N[3]==N[1]&&N[1]==N[2]){
      cout<<"Yes"<<endl;
    }
  	else{
      cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
import java.util.Scanner;

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

		while (true) {
			String[] lines = sc.nextLine().split(" ");
			int height = Integer.parseInt(lines[0]);
			int width = Integer.parseInt(lines[1]);
			if(height == 0 && width == 0) {
				break;
			} else {
				for(int i = 0;i < height;i++) {
					for(int j = 0;j < width;j++) {
						System.out.print("#");
					}
					System.out.println();
				}
				System.out.println();
			}

		}
	}
}

Measured memory_bytes: 32944
using System;
using System.Linq;

namespace ABC109_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var NX = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var N = NX[0];
            var X = NX[1];
            var x = Console.ReadLine().Split().Select(long.Parse).ToList();

            x = x.Select(a => Math.Abs(X - a)).OrderBy(a => a).ToList();

            long gcd = x[0];

            for (int i = 1; i < N; i++)
                gcd = CalcGcd(gcd, x[i]);

            Console.WriteLine(gcd);
        }

        public static long CalcGcd(long x, long y)
        {
            return ((y == 0) ? x : CalcGcd(y, x % y));
        }
    }
}


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

using namespace std;

typedef long long int lli;

const lli max_length = 1L * 1000 * 1000* 1000 * 1000;

int main() {
  int n, m, l;
  cin >> n >> m >> l;
  vector< vector<lli> > graph(n, vector<lli>(n, max_length));
  for (int i = 0; i < m; i++) {
    lli a,b,c;
    cin >> a >> b >> c;
    graph[a-1][b-1] = c;
    graph[b-1][a-1] = c;
  }

  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
      }
    }
  }
  vector< vector<lli> > graph2(n, vector<lli>(n, max_length));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (graph[i][j] <= l) {
        graph2[i][j] = 1;
      }
    }
  }

  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        graph2[i][j] = min(graph2[i][j], graph2[i][k] + graph2[k][j]);
      }
    }
  }

  int q; cin >> q;
  for (int i = 0; i < q; i++) {
    int s,t; cin >> s >> t;
    s--; t--;
    if (graph2[s][t] >= max_length) {
      cout << -1 << endl;
    } else {
      cout << graph2[s][t] - 1 << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1920
package main

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

const (
	initialBufSize = 10000
	maxBufSize     = 1000000009
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	N := nextInt()
	K := nextInt()
	Q := nextInt()
	correctanswers := make([]int, N)
	for i := 0; i < Q; i++ {
		Ai := nextInt() - 1
		correctanswers[Ai]++
	}
	for i := 0; i < N; i++ {
		score := K - Q + correctanswers[i]
		if score > 0 {
			fmt.Println("Yes")
		} else {
			fmt.Println("No")
		}
	}
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 35712
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char s[35],t[35];int cnt[35],n;
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	fp(i,1,n)++cnt[s[i]-'a'];
	if(n<26){
		printf("%s",s+1);
		fp(i,0,25)if(!cnt[i]){putchar(i+'a');break;}
		return 0;
	}
	fp(i,1,n)t[i]=s[i];
	if(!next_permutation(t+1,t+1+n))return puts("-1"),0;
	fp(i,1,n){
		putchar(t[i]);
		if(t[i]!=s[i])break;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>
#include<list>

/*
　　　　　　　　　　　　　　　　　　　　　__,.二ﾆ==-　　ﾆ．、_.　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　.,.．‐　⌒　　　　　　　　　　　　｀`'ァ-ﾆ、.　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　ィ'´.　　　　　　　　　　　　　　　　　　　　　　´丶.、　　　　　　　　　　　　
　　　　　　　　　　　.,ィ'´　　　　　　　　　　　　　　　　　　　　　　　　　　　　`.ｘ、..　　　　　　　　　
　..　　　　　　　　／.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　､＼.　　　　　　　　
　　　　　　　　.ﾝ′.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　￢`""冖ｰミト．
　　　　　　　,ｒ′.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.ﾍ、　　　　`
　　　　　　ﾂ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　`、....　　　
　　　　　./´　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ﾍ　　　　
　.....　　/.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.〉.　　　
　　　´/..　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　.ｌ　　　
　　　ｨ　　　　　　　　　　　　　　　　　　　　　　　　　．　　　　　　　　　　　　　　　　　　　　　ｆ..　　
　..　.ｆ　,d.　　　　　　　　　　　　　　　　　l　　　′　」　　,.　　　　　　　　　　　　　ﾄ　　　　　！　　
　.　〕../.ｆ..　　　　　　　　　　　　　　　　　′　．.　　|　　.｝　　　　　　　　　　　　　|　　　　　　|.　　
　　.!./..f..　　　　　　　　　　　　　　　　　/　　!－　ナ丶п冖т　　　　ﾉｰ-　．　〕　　　　　　|.　　
　　|ﾒ　|　　　　　　　　　　　　　　　｜　j　　　　　　,　　┌．　|〈.　　　л`.　　　/|..　　　　　┤,..　
　...「...｜.　　　　　　|　　´　　　　　　l.　|　　j.Ｌ......ｭ.Ｌ＿└ヽ_｜Y.　　ﾒムｗ　ょ　|　　j.:　　　|　￣
　.　　｜.　　　　　　　　　　　　　　　т〕＜.ィ冖T冖..　г‐　`､　`,　/┴￢..г￣|..　.′　　｜　　
　...　　|　　　　　　　　．..　　　　　　　),|..　｀　　ﾘ　「_ﾉ.||　　　　`　V　　|!｛,｢ll　´.」.　　　　　卜　　
　.　　｜.」　　　　　　′　　　　　　　　ヽ　　　　└++〃..　　　　　　　　ﾙｗｆ　　ｶz′.　　　｜.　　
　　　　|..〕　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　｢　　　　　．|　　　
　　　　.ｌ.|.　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　′.　　　　　|　　　
　.　　　.〕..　　　　　　　　　　　　　　　`!　　　　　　　　_...．.ｰ：''　　　　　　　　　｣　´　　　　λ.　　
　　　　_｢.　　　　,　　　　　　　　　　　　┐_,、｀~‐''"´　　　　　　　　　　　　　　　　ィ　　　.､　ﾍ、　
　　　　ｆ　　　　　　:_＿..,二ュ．-i―'''^~´　　　　　　　　　　　　　　　　　　　　　　　､＼イ　ヘ．`ｘ
　.　　/　　　　　　｛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　j　　　　.~^
　　､/　　　　　　　'ｔ..　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　丿..　　　　　
　.../.　　　　　　　,x┐..　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　∠∫　　　　　
　:^.　　　　　　　/　　￣冖ー=zzｭ┌ｰ―--　　　∟,二...＿.　　　　　　　_,､．-ｰ.'l+~.　.l｀．　　　　
　.　　　　　　　У.　　　　　　　　　⌒冖‐-=．_..　l｢.｢　　　　　　´￣｣了　　.,､-''＾　　　〉　ヽ_　　　
　　　　　　　_/.　　　　　　　　　　　　　　　　　　￣~'.ー-=．、＿,..usｧ.ｰ''"　　　　　　｛　　　＼´　
　　　　　　_ヰl'￢―-　､_　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（　　　　.＼
*/

using namespace std;

using ll = long long int;
using ull = unsigned long long int;

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n,ll mod = MOD){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%mod;
        }
        x = (x*x)%mod;
        n >>= 1;
    }
    return ret;
}

ll mygcd(ll a,ll b){
    if(b == 0)return a;
    return mygcd(b,a%b);
}

ll twoPow(ll shiftNum){
    return (1LL << (shiftNum - 1));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    ll n,k;
    cin >> n >> k;
    ++n;

    cout << ((n*n*(n+1))/2 - (n*(n+1)*(2*n+1))/6 + n - (n*(k-1)*(k))/2 + ((k-1)*k*(2*k-1))/6 - k + 1)%MOD << endl;

    return 0;
}

Measured memory_bytes: 3660
///not today

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

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef pair<long long, long long> pll;

#define SZ(x) (int)(x).size()
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define xmax(x, y) (x) = max((x), (y))
#define xmin(x, y) (x) = min((x), (y))
#define F first
#define S second
//#define int long long
#define accept_sho ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define lc (v << 1)
#define rc ((v << 1)| 1)
#define MID ((R + L) >> 1)

const int maxn = 3002;
int n, a[maxn];
bool ans[maxn], mrk[maxn];
vector <int> aj[maxn];

void dfs(int v){
      mrk[v] = true;
      int sum = 0;
      ans[v] = false;
      for(auto u : aj[v]){
            if(mrk[u]){
                  continue;
            }
            dfs(u);
            if(!ans[u] && a[u] < a[v]){
                  ans[v] = true;
            }
      }
      return;
}

bool chk(int v){
      for(int i = 0; i < n; i ++){
            mrk[i] = false;
      }
      dfs(v);
      return ans[v];
}

int main(){
      accept_sho
      cin >>n;
      for(int i = 0; i < n; i ++){
            cin >>a[i];
      }
      for(int i = 0; i < n - 1; i ++){
            int u, v;
            cin >>u >>v;
            u --;
            v --;
            aj[u].pub(v);
            aj[v].pub(u);
      }
      for(int i = 0; i < n; i ++){
            if(chk(i)){
                  cout <<i + 1 <<' ';
            }
      }
      return false;
}


Measured memory_bytes: 4004
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    int n, x, y;
    cin >> n >> x >> y;
    x--; y--;

    vector <int> ans(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dis = min(j - i, abs(i - x) + 1 + abs(j - y));
            ans[dis]++;
        }
    }

    for (int i = 1; i < n; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main() {
  int n, t = 0, i;
  int a[1000];
  scanf("%d",&n);
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
  for (i = 0; i < n; i++) {
    if (a[i] % 2 == 0 ) {
      if (a[i] % 5 == 0 || a[i] % 3 == 0) {

      } else {
        t++;
        break;
      }
    }
  }
  if (t == 0)
    printf("APPROVED\n");
  else
    printf("DENIED\n");
  return 0;
}

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

int main() {
	int num[3];
	cin >> num[0] >> num[1] >> num[2];

	int count = 0;

	vector <int> even_num;
	vector <int> odd_num;
	
	for (int i = 0; i < 3; i++) {
		if (num[i] % 2 == 0)even_num.push_back(num[i]);
		else odd_num.push_back(num[i]);
	}
	sort(even_num.begin(), even_num.end());
	sort(odd_num.begin(), odd_num.end());

	if (even_num.size() == 3) {
		auto itr = even_num.begin();
		auto itr_end = even_num.end();
		itr_end--;
		count += (*itr_end - (*itr)) / 2;
		itr++;
		count += (*itr_end - (*itr)) / 2;
	}
	else if (even_num.size() == 2) {
		auto even_itr = even_num.begin();
		odd_num.push_back(*even_itr + 1);
		even_itr++;
		odd_num.push_back(*even_itr + 1);
		sort(odd_num.begin(), odd_num.end());
		count++;

		auto odd_itr = odd_num.begin();
		auto odd_itr_end = odd_num.end();
		odd_itr_end--;
		count += (*odd_itr_end - *odd_itr) / 2;
		odd_itr++;
		count += (*odd_itr_end - *odd_itr) / 2;
	}
	else if (even_num.size() == 1) {
		auto odd_itr = odd_num.begin();
		even_num.push_back(*odd_itr + 1);
		odd_itr++;
		even_num.push_back(*odd_itr + 1);
		sort(even_num.begin(), even_num.end());
		count++;

		auto even_itr = even_num.begin();
		auto even_itr_end = even_num.end();
		even_itr_end--;
		count += (*even_itr_end - *even_itr) / 2;
		even_itr++;
		count += (*even_itr_end - *even_itr) / 2;
	}
	else {
		auto itr = odd_num.begin();
		auto itr_end = odd_num.end();
		itr_end--;
		count += (*itr_end - (*itr)) / 2;
		itr++;
		count += (*itr_end - (*itr)) / 2;
	}

	cout << count;

	return 0;
}

Measured memory_bytes: 256
n,q = list(map(int, input().split()))
s = input()
question = [list(map(int, input().split())) for _ in range(q)]
ac = []
amount = 0
for i in range(len(s)):
  if(i == 0):
    ac.append(0)
    continue
  if(s[i-1] == "A" and s[i] == "C"):
    amount +=1
  ac.append(amount)
for r, l in question:
  print(ac[l-1] - ac[r-1])


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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

	int A,B,C; cin >> A >> B >> C;

	if(A+B >= C) cout << "Yes\n";
	else cout << "No\n";	

	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int x,a,b;
	cin>>x>>a>>b;
	a=fabs(x-a);
	b=fabs(x-b);
	if(a<=b)
		cout<<"A";
	else
		cout<<"B";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using ll = long long;

int main() {
    int x , y;
    cin >> x >> y;

    bool ans = true;
    if (x * 2 <= y && y <= x * 4 && y % 2 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>

int n,A[2000];

int search ( int i , int m ){
  int res;
  if ( m == 0 ){
    return 1;
  }
  if ( i >= n ){
    return 0;
  }
  res = search( i + 1 , m ) || search( i + 1 , m - A[i]);
  return res;
}

int main ( void ){
  int q,m,i;
  scanf( "%d" , &n );
  for( i = 0 ; i < n ; i++ ){
    scanf( "%d" , &A[i]);
  }
  scanf( "%d" , &q );
  for ( i = 0 ; i < q ; i++ ){
    scanf( "%d" , &m );
    if ( search( 0 , m )){
      printf( "yes\n" );
    }
    else{
      printf( "no\n" );
    }
  }
  return 0;
}

Measured memory_bytes: 580
N=int(input())
a=[]
b=[]
c=[]
dp=[]
for i in range(N):
    temp=list(map(int,input().split()))
    a.append(temp[0])
    b.append(temp[1])
    c.append(temp[2])
dp.append([a[0],b[0],c[0]])
for i in range(1,N):
    dp.append([max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]),max(dp[i-1][0]+b[i],dp[i-1][2]+b[i]),max(dp[i-1][0]+c[i],dp[i-1][1]+c[i])])
print(str(max(dp[N-1][0],dp[N-1][1],dp[N-1][2])))

Measured memory_bytes: 34628
import java.util.*;

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

      int[] arr   = new int[3];
      int   count = 0;
      for(int i = 0; i < 3; i++){
          arr[i] = scan.nextInt();
          }
      Arrays.sort(arr);
      if((arr[1] - arr[0]) % 2 == 0){
         count += (arr[1] - arr[0]) / 2;
         count += arr[2] - arr[1];
         }
      else{
          count += (arr[2] - arr[0]) / 2;
          count += (arr[2] - arr[1]) / 2 + 2;
          }

      System.out.println(count);
   }
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
vb dp(10000);
int main() {
	dp[0] = true;
	int n; cin >> n;
	vi a(n); rep(i, 0, n) cin >> a[i];
	rep(i, 0, n) {
		rrep(j, 2000, -1) {
			if(dp[j]) dp[j + a[i]] = true;
		}
	}
	int q; cin >> q;
	int m;
	rep(i, 0, q) {
		cin >> m;
		P(dp[m] ? "yes" : "no");
	}
	return 0;
}

Measured memory_bytes: 3172
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d)) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  vector<bool> chk(3, false);
  for(int i = 0; i < 3; i++){
    if(s[i] == 'a') chk[0] = true;
    else if(s[i] == 'b') chk[1] = true;
    else chk[2] = true;
  }
  if(chk[0] && chk[1] && chk[2])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
import math

N, K = map(int, input().split())
if K <= N:
  p = 1 - (K-1)/N
else:
  p = 0
for i in range(1, min(N+1, K)):
  n = math.ceil(math.log(K/i, 2))
  p += 1/N * (1/2 ** n)
print(p)

Measured memory_bytes: 3060