akhauriyash/Code-Regression huggingface dataset:
// 解き直し.
// ABC 132解説.
// https://img.atcoder.jp/abc132/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
const int MAX_V = 1e5;
int memo[321123];
vector<int> graph[321123];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// グラフを幅優先探索する.
// ※bfsの動作確認用.
// @param s: 探索開始の頂点番号.
// @param g: 探索終了の頂点番号.
// @return: 特に無し.
void bfs(int s, int g){

    // 1. 空のキュー.
    queue<int> q;

    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;

    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    
    // 4. キュー q が 空になるまで, 探索.
    while(!q.empty()) {
        
        // 5. 頂点 u を キュー q から取り出す.
        int u = q.front();
        q.pop();
        
        // 6. 頂点 u が ゴールだったら終了.
        if(u == g) break;
        
        // 7. 取り出した要素を処理.
        for(auto &e : graph[u]){
            // 7-1. 頂点u の 隣接する頂点e が, 未訪問だったら, キュー q に追加.
            if(memo[e] == 0 && e != s){
                // 頂点e を キュー q に追加.
                q.push(e);
                // 頂点e に 距離memo[u] プラス 1 を 加算.
                memo[e] += memo[u];
                memo[e]++;
            }
        }
    }
}

int main() {

    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);

    // 2. グラフ作成.
    // 解説通り, グラフを3倍化？してみる.
    // 3辺 u0 -> v1, u1 -> v2, u2 -> v0 を 張る.
    // 具体的には, 
    // u0 = u + i * 3, u1 = u + 1, u2 = u + MAX_V * 2
    // v0 = v, v1 = v + MAX_V, v2 = v + MAX_V * 2
    for(int i = 0; i < M * 3; i += 3){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        // u0 -> v1
        graph[u].push_back(v + MAX_V * 1);
        // u1 -> v2
        graph[u + MAX_V * 1].push_back(v + MAX_V * 2);
        // u2 -> v0
        graph[u + MAX_V * 2].push_back(v);
    }
    
    // 3. スタート地点, ゴール地点.
    int S, T;
    scanf("%d %d", &S, &T);
    S--, T--;
    
    // 4. S0 -> T0 の 最短距離 を 計算.
    bfs(S, T);
    // for(int i = 0; i < N * 3; i++) cout << memo[i] << " ";
    // cout << endl;
    
    // 5. 後処理.
    int ans = memo[T] / 3;
    if(ans == 0) printf("%d\n", -1);
    else         printf("%d\n", ans);
    return 0;

}

Measured memory_bytes: 18304
local a, b = io.read("*n", "*n", "*l")
local s = io.read()
local f = true
for i = 1, #s do
  if i == a + 1 then
    if s:sub(i, i) ~= "-" then f = false break end
  else
    local c = s:sub(i, i):byte()
    if c < 48 or 57 < c then
      f = false
      break
    end
  end
end
print(f and "Yes" or "No")


Measured memory_bytes: 760
# -*- coding: utf-8 -*-

N = int(input().strip())
W_list = [input().strip() for _ in range(N)]
#-----

for i in range(len(W_list)-1):
    if W_list[i+1] not in W_list[:(i+1)]  and  W_list[i][-1]==W_list[i+1][0]:
        continue
    else:
        print("No")
        break

else:
    print("Yes")


Measured memory_bytes: 3060
import java.util.*;
public class Main{
  public static void main(String[] args)
  {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int[] a=new int[n*2];
    for(int i=0;i<n*2;i++)
    {
        a[i]=sc.nextInt();
    }
    int ans=0;
    for(int j=0;j<=(n*2)-6;j++)
    {
      if(a[j]==a[j+1])
      {
         if(a[j+2]==a[j+3])
         {
           if(a[j+4]==a[j+5])
           {
               ans=1;
           }
         }
      }
    }
    if(ans==1)
      	System.out.println("Yes");
    else
      System.out.println("No");
      
  }
}
  
  

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

int main(){
  int n;
  cin >> n;
  int b[n-1];
  for (int i = 0; i < n-1; i++){
    cin >> b[i];
  }
  int res = 0;
  res += b[0];
  for (int j = 0; j < n-2; j++){
  	res += min(b[j], b[j+1]);
  }
  res += b[n-2];
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iomanip>

#include <map>
#include <set>
#include <queue>
#include <stack>

#define ALL(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdbl vector<double>
#define vstr vector<string>
#define push_back pb
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	int N;
	cin >> N;

	ll a[3*N];
	rep(i,3*N) cin >> a[i];

	sort(a,a+3*N);

	ll ans = 0;
	for(int i = N;i< 3*N;i+=2) ans += a[i];

	cout << ans << endl;
}

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

#define INF INT_MAX
#define UINF UINT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef std::pair<int,int> pii;

using namespace std;

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

    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> memo(n,0);
    vector<ll> kumi(n,0);
    REP(i,n){
        cin >> a[i];
        a[i]--;
        memo[a[i]]++;
    }

    ll sum = 0;
    REP(i,n){
        if(memo[i] > 1)sum += memo[i]*(memo[i]-1)/2;
    }

    REP(i,n){
        if(memo[a[i]] > 1)cout << sum - (memo[a[i]] - 1) << endl;
        else cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	ll n, d;
	cin >> n >> d;
	d = d * d;
	vector<pair<ll,ll>>xy(n);
	for (int i = 0; i < n; i++) {
		cin >> xy.at(i).first >> xy.at(i).second;
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ll xkyori = xy.at(i).first * xy.at(i).first;
		ll ykyori = xy.at(i).second * xy.at(i).second;
		if (xkyori + ykyori <= d)ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 6380
#include <stdio.h>
#define limit 100001

long N,M,ans = 0;
long par[limit],rank[limit];

void init(long n){
  for(int i = 0;i < n;i++){
    par[i] = i;
    rank[i] = 0;
  }
}

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

int same(long x,long y){
  if(root(x) == root(y)) return 1;
  else return 0;
}

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

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

int main(void){
  long x,y;
  scanf("%ld%ld",&N,&M);
  long p[N+1];

  init(N);
  for(int i = 1;i <= N;i++){
    scanf("%ld",&p[i]);
  }
  for(int i = 0;i < M;i++){
    scanf("%ld%ld",&x,&y);
    unite(x,y);
  }

  for(int i = 1;i <= N;i++){
    if(same(p[i],i)) ans++;
  }

  printf("%ld\n",ans);

  return 0;
}

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

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

fn main() {
    let n: usize = read();
    let a: Vec<i64> = read_vec();
    let mut pos = vec![0; n + 1];
    for i in 0..n {
        pos[a[i] as usize] = i;
    }

    let mut pr = vec![0i32; n + 1];
    let mut nr = vec![0i32; n + 1];
    for x in 0..n {
        pr[x] = x as i32 - 1;
        nr[x] = x as i32 + 1;
    }

    let mut ans = 0i64;
    for i in (1..n + 1).rev() {
        let x = pos[i];
        let v = x as i64;
        let n = nr[x];
        let p = pr[x];
        ans += i as i64 * (v - p as i64) * (n as i64 - v);

        if n >= 0 {
            pr[n as usize] = p;
        }
        if p >= 0 {
            nr[p as usize] = n;
        }
    }
    println!("{}", ans);
}
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

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


Measured memory_bytes: 9716
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  string s;cin >> s;
  int q;cin >> q;
  vector<int> t(q);
  vector<int> f(q);
  vector<char> c(q);
  rep(i,q){
    cin >> t[i];
    if(t[i]==2){
      cin >> f[i] >> c[i];
    }
  }

  string fr="",ba="";
  int p=0;
  rep(i,q){
    if(t[i]==1) p = (p+1)%2;
    else{
      if(p==0){
	if(f[i]==1) fr.push_back(c[i]);
	else ba.push_back(c[i]);
      }
      else{
	if(f[i]==1) ba.push_back(c[i]);
	else fr.push_back(c[i]);
      }
    }
  }
  if(p==0){
    reverse(fr.begin(), fr.end());
    cout << fr << s << ba << "\n";
  }
  else{
    reverse(s.begin(), s.end());
    reverse(ba.begin(), ba.end());
    cout << ba << s << fr << "\n";
  }

  
  return 0;
}


Measured memory_bytes: 2880
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <math.h>
#define ll long long
ll gcd(ll a,ll b){
    ll s=1,c;
    while(a&&b){
        if((~a&1)&&(~b&1))
            a>>=1,b>>=1,s<<=1;
        else if(~a&1)a>>=1;
        else if(~b&1)b>>=1;
        else if(a>b)a=a-b;
        else c=b-a,b=a,a=c;
    }
    if(!a)return b*s;
    if(!b)return a*s;
}
using namespace std;
int main(){
	ll n;cin>>n;
	ll ans=0;
	for(int i=0;i<=n;i++){
		if(i==n){
			cout<<-1;
			break;
		}
		ans=ans*10+7;
		ans=ans%n;
		if(ans==0){
			cout<<i+1;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 3652
(defun f(lst)
  (labels ((rec (lst i n)
				(if (null lst)
				  1
				(if (= i n)
				  (* 1 (rec (cdr lst) (1+ i) n))
				  (* (car lst) (rec (cdr lst) (1+ i) n))))))
	(loop for i from 0 to (1- (length lst)) collect (rec lst 0 i))))
(defun g(lst)
  (/ (reduce #'* lst) (reduce #'+ (f lst))))

(defun splitat (c line)
  (labels ((rec (line acc)
				(let ((pos (position-if (lambda(cc) (char= c cc)) line)))
				  (if pos
					  (rec (subseq line (1+ pos)) (cons (subseq line 0 pos) acc))
					(nreverse (cons line acc))))))
	(rec line nil)))
(defun gg()
  (let* ((n (read-line nil nil))
		 (lst (mapcar #'parse-integer (splitat #\space (read-line nil nil)))))
	(format t "~f~%" (g lst))))
(gg)


Measured memory_bytes: 16356
(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  console.log(' ' + buildMaxHeap(lines.shift().split(' ').map(Number)).join(' '));
})();

function buildMaxHeap(arr) {
  const n = arr.length;
  const maxHeapify = (i) => {
    let left, right, largest = i;
    left = 2 * i + 1;
    right = 2 * i + 2;
    if (left >= n && right >= n) return;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
      arr[largest] = [arr[i], arr[i] = arr[largest]][0];
      maxHeapify(largest);
    }
  };

  for (let i = Math.floor(arr.length / 2); i >= 0; i--) maxHeapify(i);
  return arr;
}



Measured memory_bytes: 110716
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define repc(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

i64 sqr(i64 n) { return n * n; }

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(ios_base::fixed);
    cout.precision(12);

    var(int, N, D);
    auto x = makeV(0, N, D);
    rep(i, 0, N) { read(x[i]); }

    int cnt = 0;
    rep(i, 0, N) rep(j, i + 1, N) {
        i64 sum = 0;
        rep(k, 0, D) { sum += sqr(x[i][k] - x[j][k]); }
        const i64 p = sqrt(sum);
        if (p * p == sum) ++cnt;
    }

    print(cnt);

    return 0;
}


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

int main()
{
	int x,y;
	int i=0,j=0,s=0;
	cin >> x >> y;
	while(1)
	{
		i++;
		j++;
		if((i==x&&j>y)||(i>x&&j==y)||(i>x&&j>y)||(i>x&&j<y))//||(i<x&&j>y)
		{
			cout << s;
			return 0;
		}
		s++;
	}
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
#define int long long
#define vint vector<int>
#define pint pair<int, int>
#define pb(a) push_back(a)
#define all(v) v.begin(), v.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl

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

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

	int a;
	string s;

	cin >> a >> s;

	if (a >= 3200) {
		cout << s << endl;
	} else {
		cout << "red" << endl;
	}

	return 0;
}

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

int main(){
  int nae[110],n,d,ans;
  while(1){
    scanf("%d",&n);
    if(n==0) break;

    for(int i=0;i<=n;i++){
      scanf("%d",&nae[i]);
    }

    for(int i=1;i<n;i++){
      if(nae[i]-nae[i-1]!=nae[i+1]-nae[i]){
	if(i==n-1||nae[i+2]-nae[i]==nae[i]-nae[i-1]){
	  printf("%d\n",nae[i+1]);
	  break;
	}else if(nae[i+1]-nae[i-1]!=nae[i+2]-nae[i+1]){
	  printf("%d\n",nae[i-1]);
	  break;
	}else{
	  printf("%d\n",nae[i]);
	  break;
	}
      }
    }
  } 
  return 0;
}



Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s,t;
    cin>>s>>t;
    ll count=0;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i]!=t[i])
        {
            count++;
        }
    }
    cout<<count;
    
    return 0;
}

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

int main() {
    int a, b;
    char op;
    while (true) {
        cin >> a >> op >> b;
        if (op == '?') {
            break;
        }
        switch (op){
            case '+':
                cout << a + b << endl;
                break;
            case '-':
                cout << a - b << endl;
                break;
            case '*':
                cout << a * b << endl;
                break;
            case '/':
                if (b == 0) {
                    break;
                }
                cout << a / b << endl;
                break;
        }
    }
    return 0;
}


Measured memory_bytes: 3096
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
namespace AtCoder.ARC078
{
    class SplittingPile
    {
        public static void Main()
        {
            var n = int.Parse(ReadLine());
            var cards = ReadLine().Split(' ').Select(_ => long.Parse(_)).ToArray();
            var sum = cards.Sum();
            long min = long.MaxValue;
            long s = 0;
            for (var i = 0; i < cards.Length - 1; ++i) {
                s += cards[i];
                if (min > Math.Abs(sum - s - s)) {
                    min = Math.Abs(sum - s - s);
                }
            }
            WriteLine(min);
        }
    }
}


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

int main() {
  int K, S;
  cin >> K >> S;
  int ans = 0;
  for (int X = 0; X <= K; ++X) {
    for (int Y = 0; Y <= K; ++Y) {
      int Z = S - X - Y;
      if (0 <= Z && Z <= K) {
        ++ans;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char s1[11],s2[11];
long long n;
int main(){
    cin>>n;
    for(int i=sqrt(n);i>=1;i--)
        if(n%i==0){
            sprintf(s1,"%d",i);
            sprintf(s2,"%d",n/i);
            cout<<max(strlen(s1),strlen(s2))<<endl;
            break;
        }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

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

    int n,m;

    cin >> n >> m;

    vector<int> a(n);

    for(int i = 0;i < n;i++) cin >> a[i];

    sort(a.begin(),a.end());

    int x = 0;

    for(int i = 0;i < n;i++)
    {
        if(x+a[i]<=m) x+=a[i];
        else{ cout << i; return 0; }
    }

    if(x<m) cout << n-1;
    else cout << n;
}


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

using namespace std;

const vector<int> num = {5, 7, 5, 7, 7};

bool Check(int idx, const int n, const vector<int> &w) {
    int j = 0, sum = 0;
    for (int i = idx; i < n && j < 5; ++i) {
        sum += w[i];
        if (num[j] == sum) {
            ++j;
            sum = 0;
        }
        else if (num[j] < sum)
            return true;
    }

    return (j == 5) ? false : true;
}

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

    int n;
    string s;

    while (cin >> n, n) {
        vector<int> w(n);
        for (int i = 0; i < n; ++i) {
            cin >> s;
            w[i] = s.size();
        }

        int idx = 0;
        while (Check(idx, n, w))
            ++idx;

        cout << idx + 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 3116
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
int n,a;
cin>>n;
int max=-1000001;
int min=1000001;
long sum=0;
for(int i=0;i<n;i++){
cin>>a;
sum=sum+a;
if(max<a)max=a;
if(min>a)min=a;
}
cout<<min<<" "<<max<<" "<<sum<<endl;
}
    

Measured memory_bytes: 1168
#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
 
typedef long long ll;

#define rep(i,n) for(ll i = 0; i < n; i++)
 
using namespace std;
 
const ll INF = ll(1e18)+1;
const double PI=3.14159265358979323846;
int dp[10500];

int main(){
  int N,W,v[1001]={},w[1001]={};
  cin >> N >> W;
  rep(i,N) cin >> v[i] >> w[i];

  rep(i,N){
    rep(j,W){
      dp[j+w[i]] = max(dp[j+w[i]], dp[j]+v[i]);
    }
  }
  cout << dp[W] << endl;
}



Measured memory_bytes: 3180
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;
const int L = 5;


int N, v[L][L][L], t[L][L][L], c = 1;

int main() {
  while(cin >>N && N){
    if(c != 1) cout <<endl;
    REP(z, L){
      REP(y, L){
        string s; cin >>s;
        REP(x, L) v[z][y][x] = s[x] - '0';
      }
    }
    int MA; cin >>MA; vector<int> A(MA); REP(i, MA) cin >>A[i];
    int MB; cin >>MB; vector<int> B(MB); REP(i, MB) cin >>B[i];
    REP(n, N){
      REP(z, L){
        REP(y, L){
          REP(x, L){
            int cnt = 0;
            FOR(mz, -1, 2) FOR(my, -1, 2) FOR(mx, -1, 2) if(!(mz == 0 && my == 0 && mx == 0) && z + mz >= 0 && y + my >= 0 && x + mx >= 0 && z + mz < L && y + my < L && x + mx < L) cnt += v[z + mz][y + my][x + mx];
            if(v[z][y][x]){
              int f = 0;
              REP(i, MB) if(cnt == B[i]) f = 1;
              t[z][y][x] = f;
            } else{
              int f = 0;
              REP(i, MA) if(cnt == A[i]) f = 1;
              t[z][y][x] = f;
            }
          }
        }
      }
      REP(i, L) REP(j, L) REP(k, L) v[i][j][k] = t[i][j][k];
    }
    cout <<"Case " <<c++ <<":" <<endl;
    REP(z, L){
      REP(y, L){
        REP(x, L) cout <<v[z][y][x];
        cout <<endl;
      }
      if(z + 1 != L) cout <<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1212
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	    String line = br.readLine();
	    int a = Integer.parseInt(line.split(" ")[0]);
	    int b = Integer.parseInt(line.split(" ")[1]);
	    int c = Integer.parseInt(line.split(" ")[2]);

	    int count = 0;
	    for (int i = a; i <= b; i++) {
	    	if (c % i == 0) {
	    		count++;
	    	}
	    }

	    System.out.println(count);

	}
}

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

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

int n;
ll a[444];
ll b[444];
ll dp[444][444];

ll dfs(int l, int r){
	if(dp[l][r] != 0)return dp[l][r];
	if(l == r)return 0;
	ll ret = LLINF;
	for(int i = l;i < r;i++){
		ret = min(ret,dfs(l,i) + dfs(i+1,r) + b[r] - b[l-1]);
	}
	return dp[l][r] = ret;
}

int main(){
	
	cin >> n;
	REP(i,n){
		cin >> a[i+1];
		b[i+1] = a[i+1];
		b[i+1] += b[i];
	}
	
	cout << dfs(1,n) << endl;
	
	return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF LLONG_MAX/5
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
vector<int> v[100010];
int x[100010];
bool used0[100010],used1[100010];
int mypow(int a,int b,int c){
	if(b==0)return 1;
	if(b%2)return mypow(a,b-1,c)*a%c;
	int z=mypow(a,b/2,c);
	return z*z%c;
}
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
void mutu(int z,int y){
	used0[z]=true;
	x[z]=y;
	f(i,v[z].size()){
		if(!used0[v[z][i]])mutu(v[z][i],y+1);
	}
}
void mutu1(int z,int y){
	if(x[z]<=y)return;
	used1[z]=true;
	f(i,v[z].size()){
		if(!used1[v[z][i]])mutu1(v[z][i],y+1);
	}
}
signed main(){
	int a,b,c,ans=0;
	cin>>a>>b>>c;
	f(i,a-1){
		int d,e;
		cin>>d>>e;
		v[d].push_back(e);
		v[e].push_back(d);
	}
	mutu(c,0);
	mutu1(b,0);
	f(i,a){
		if(used1[i+1])ans=max(ans,x[i+1]-1);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 10752
import sys
sys.setrecursionlimit(2000)

def DFS(p):
    if len(p)>=N:
        pat.append(p[:])
        return
    for i in range(2):
        p.append(i)
        DFS(p)
        p.pop()

N=int(input())
xy=[]
for i in range(N):
    A=int(input())
    x=[list(map(int,input().split())) for _ in range(A)]
    xy.append(x)

ans=0
p=[]
pat=[]
DFS(p)

for p in pat:
    cond=True
    for k in range(N):
        if p[k]==1:
            for h in xy[k]:
                if p[h[0]-1]!=h[1]:
                    cond=False
    if cond:
        ans=max(ans,sum(p))

print(ans)

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

ans = []

if N == 0:
    print('0')
else:
    while abs(N) > 0:
        r = N % -2
        if r != 0:
            N -= 1
            ans.append('1')
        else:
            ans.append('0')

        N //= -2

    print("".join(reversed(ans)))

Measured memory_bytes: 3060
/**
 *      ABC 70 B
 *      author  : kyomukyomupurin
 *      created : 2018-09-04 22:54:36
**/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A, B, C, D; cin >> A >> B >> C >> D;
    min(B, D) > max(A, C) ? cout << min(B, D) - max(A, C) : cout << 0;
    return 0;
}


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

int main(void) {
    int n;
    cin >> n;
    ll a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ll d[n-1];
    for (int i = 0; i < n-1; i++) {
        d[i] = a[i+1] - a[i];
        if (d[i] < 0) {
            d[i] = -1;
        } else if (d[i] > 0) {
            d[i] = 1;
        } else {
            d[i] = 0;
        }
    }
    int stat = d[0], end = 0;
    for (int i = 0; i < n-1; i++) {
        if (d[i] == 1) {
            if (stat == -1) {
                end++;
                stat = 0;
            } else {
                stat = 1;
            }
        }
        if (d[i] == -1) {
            if (stat == 1) {
                end++;
                stat = 0;
            } else {
                stat = -1;
            }
        }
    }
    end++;

    cout << end << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <stack>
#include <complex>
#include <ctime>
#include <unordered_map>
#pragma comment (linker, "/STACK:256000000")

using namespace std;

long long calc(long long ai, long long aj, long long al) {
	long long res = 4LL * ((ai / 2) + (aj / 2) + (al / 2));
	if (ai % 2 == 1 && aj % 2 == 1 && al % 2 == 1) {
		res += 6;
	}
	return res;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	long long ai, ao, at, aj, al, as, az;
	cin >> ai >> ao >> at >> aj >> al >> as >> az;

	long long res = 2LL * ao;

	long long u = calc(ai, aj, al);
	for (long long t = 1; t <= 100; ++t) {
		if (ai >= t && aj >= t && al >= t) {
			u = max(u, calc(ai - t, aj - t, al - t) + 6LL * t);
		}
	}

	res += u;

	cout << (res / 2) << endl;


	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int x,y,a,b,c;
  cin >> x >> y>> a >> b >> c;
    vector<long long> apple;
    vector<long long> r_app;
    vector<long long> g_app;
    vector<long long> app;
    for(int i=0;i<a;i++)
    {
      long long p;
      cin >> p;
      r_app.push_back(p);
    }
    for(int i=0;i<b;i++)
    {
      long long p;
      cin >> p;
      g_app.push_back(p);
    } 
    for(int i=0;i<c;i++)
    {
      long long p;
      cin >> p;
      app.push_back(p);
    }
    sort(r_app.rbegin(),r_app.rend());
    sort(g_app.rbegin(),g_app.rend());
    sort(app.rbegin(),app.rend());
    vector<int> out;
    for(int i=0;i<x;i++)
      {
        out.push_back(r_app[i]);
      }
    for(int i=0;i<y;i++)
      {
        out.push_back(g_app[i]);
      }
    for(int i=0;i<c;i++)
      {
        out.push_back(app[i]);
      }

    sort(out.rbegin(),out.rend());
    long long sum = 0;
    for(int i=0;i<x+y;i++)
    {
      sum = sum + out[i];
    }
    cout << sum;
}  

Measured memory_bytes: 4724
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4,sse4.1,sse4.2,avx,tune=native")
#include <bits/stdc++.h>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amax(T& a,T b){ a = max<T>(a, b);}


int main(){
	//cin.tie(0); ios_base::sync_with_stdio(false);
	ll n , ans=0;
	cin >>n;
	VL a(5);
	rep(i, 5) cin >>a[i];
	
	ll mn= *min_element(all(a));
	
	if(mn >= n) ans = 5;
	else ans = (n+mn-1) / mn + 4;
	cout << ans <<"\n";
	
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define name(x) #x
using namespace std;


const int INF = INT_MAX;
const long long INFL = (1LL<<40);
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}




const ll MAX_SIZE = 10005;
ll memo[MAX_SIZE][2][105];
string K;
ll D;
VV(ll) A;



int main() {
    
    
   
    cin >> K;
    cin >> D;
    
    // Kの桁分解。
    vector<ll> dig;
    vector<ll>cumsum;
    dig.push_back((K[0]-'0'));
    for(auto i = 1; i<K.size(); i++){
        dig.push_back(K[i] - '0');
    }
    cumsum.push_back(dig[0]%D);
    for(auto i = 1; i<K.size(); i++){
        cumsum.push_back((cumsum[i-1]+dig[i])%MOD);
    }
    
    
    reverse(all(dig));
    reverse(all(cumsum));
    ll N = (ll)K.size();
    
    memo[N-1][1][dig[N-1]%D] = 1;
    for(auto i = 0; i<dig[N-1];i++){
        memo[N-1][0][i%D] += 1;
        memo[N-1][0][i%D] %=MOD;
    }
    
    for(auto n = N-2;n>=0;n--){
        memo[n][1][cumsum[n]%D] = 1;
        for(auto i =0; i<D; i++){
            for(auto j = 0; j<dig[n];j++){
                memo[n][0][(i+j)%D] += memo[n+1][1][i];
                memo[n][0][(i+j)%D] %=MOD;
            }
            
            for(auto j = 0; j<10;j++){
                memo[n][0][(i+j)%D] += memo[n+1][0][i];
                memo[n][0][(i+j)%D] %=MOD;
            }
        }

    }
    
    ll ans = (memo[0][1][0] + memo[0][0][0] - 1);
    
    if(ans <0) ans += MOD;
    
    cout << ans %MOD << endl;
    
    return 0;
}











Measured memory_bytes: 17024
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[100000],ans,sign[100000],s;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(i==0)continue;
        if(a[i-1]<a[i])sign[i]=1;
        if(a[i-1]==a[i])sign[i]=0;
        if(a[i-1]>a[i])sign[i]=-1;
    }
    for(int i=1;i<n;i++){
        if(s==0)s=sign[i];
        if(s*sign[i]==-1){
            ans++;
            // i++;
            s=0;
        }
    }
    cout<<ans+1<<endl;
    return 0;
}

Measured memory_bytes: 1024
s = int(input())


l =[s]

for i in range(1000):
  if l[i] % 2==0:
    l.append(int(l[i] /2))
  else:
    l.append(int(3* l[i] +1))
    
ans =0

for i in range(len(l)):
  if l[i] in l[:i]:
    ans = i
    break
print(ans + 1)



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int N;
bool flag;
ll A[100000];
vector<int> G[100000];
int used[100000];

map<P, ll> dp;

ll dfs(P n) {
	if (dp[n]) {
		return dp[n] - 1;
	}
	int from = n.first, to = n.second;
	used[to] = 1;
	bool f = true;
	ll res = A[to] * 2;
	for (int v : G[to]) {
		if (used[v] == 0) {
			res -= dfs(P(to, v));
			f = false;
		}
	}
	if (res < 0) {
		flag = false;
	}
	if (f) {
		res /= 2;
	}
	used[to] = 0;
	dp[n] = res + 1;
	return res;
}


int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0, a, b; i < N - 1; i++) {
		cin >> a >> b;
		G[a - 1].push_back(b - 1);
		G[b - 1].push_back(a - 1);
	}
	flag = true;
	for (int i = 0; i < N; i++) {
		if (G[i].size() > 2) {
			ll sum = 0;
			for (int v : G[i]) {
				sum += A[v];
			}
			sum -= A[i] * 2;
			for (int v : G[i]) {
				if (A[v] > A[i]) {
					sum -= A[v] - A[i];
				}
			}
			if (sum < 0) {
				flag = false;
				break;
			}
		}
		else if (G[i].size() == 2 && (A[G[i][0]] < A[i] || A[G[i][1]] < A[i])) {
			flag = false;
			break;
		}
		else if (G[i].size() == 1 && A[G[i][0]] < A[i]) {
			flag = false;
			break;
		}
	}
	for (int i = 0; i < N; i++) {
		used[i] = 1;
		ll val = A[i] * 2;
		for (int v : G[i]) {
			val -= dfs(P(i, v));
		}
		used[i] = 0;
		if ((G[i].size() == 1 && val != A[i]) || (G[i].size() > 1 && val != 0)) {
			flag = false;
		}
	}
	cout << (flag ? "YES" : "NO") << endl;
	return 0;
}


Measured memory_bytes: 27392
using System;
using System.Collections.Generic;
using System.Linq;

namespace _0603
{
	class Program
	{
		static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int count = 1;
			List<int> list = new List<int>();
			for (int i = 1; i < n; i++)
			{
				if (x[i] == x[i - 1])
				{
					list.Add(count);
					count = 1;
				}
				else count++;
			}
			list.Add(count);
			if (list.Count < 3) Console.WriteLine(n);
			else
			{
				int max = 0;
				for (int i = 0; i < list.Count - 2; i++)
				{
					int now = 0;
					for (int j = 0; j < 3; j++)
					{
						now += list[i + j];
					}
					max = Math.Max(max, now);
				}
				Console.WriteLine(max);
			}
		}
	}
}


Measured memory_bytes: 26268
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
using namespace std;
using Graph = vector<vector<int>>;
using P = pair<long, long>;

long modpow(long a, long n, long mod) {
    long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
long modinv(long a, long mod) {
    return modpow(a, mod - 2, mod);
}

struct compare1 { 
    bool operator()(const pair<long, long>& value,  
                                const long& key) 
    { 
        return (value.first < key); 
    } 
    bool operator()(const long& key,  
                    const pair<long, long>& value) 
    { 
        return (key < value.first); 
    } 
}; 

int main()
{
    int H, W, K; cin >> H >> W >> K;
    int S[15][1005];
    string s;
    REP(i, H){
        cin >> s;
        REP(j, W) S[i][j] = (int)(s[j] - '0');
    }
    int index[600][10];
    int all = 1;
    REP(i, H-1) all *= 2; 
    //cout << all << endl;
    REP(i, all){
        int temp[10], temp2;
        temp2 = i;
        REP(j, H-1){
            temp[j] = temp2%2;
            temp2 /= 2;
            //cout << temp[j] << " ";
        }
        //cout << endl;
        index[i][0] = 0;
        REP(j, H-1) index[i][j+1] = index[i][j] + temp[j];
    }
    /*
    REP(i, all){
        REP(j, H) cout << index[i][j] << " ";
        cout << endl;
    }*/
    int ans = 10000, temp_ans;
    int milk[10], allmilk[10];
    bool flag;
    REP(i, all){
        temp_ans = index[i][H-1];
        //cout << temp_ans << " ";
        REP(j, H) allmilk[j] = 0;
        REP(j, W){
            flag = false;
            REP(k, H) milk[k] = 0;
            REP(k, H) if(S[k][j] == 1) milk[index[i][k]]++;
            //REP(k, H) cout << milk[index[i][k]] << " ";
            //cout << endl;
            REP(k, H) if(milk[k] > K){
                flag = true;
                break;
            }
            if(flag) break;
            REP(k, H) allmilk[k] += milk[k];
            REP(k, H)
                if(allmilk[k] > K){
                    temp_ans++;
                    REP(l, H) allmilk[l] = milk[l];
                    break;
                }
        }
        if(!flag) ans = min(ans, temp_ans);
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
h, w, d = map(int, input().split())
# 座標記録
cords = [0] * (h*w+1)
for i in range(h):
    line = tuple(map(int, input().split()))
    for j in range(w):
        cords[line[j]] = (i, j)

# グループごとの累積和
acccosts = [0] * (h*w+1)
for num in range(1, h*w+1-d):
    nxy = cords[num]
    nnxy = cords[num+d]
    acccosts[num+d] = acccosts[num] + abs(nxy[0]-nnxy[0]) + abs(nxy[1] - nnxy[1])

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(acccosts[r] - acccosts[l])

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

using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  if( a%3 == 0 || b%3 == 0 || (a+b)%3 == 0 ){
    cout << "Possible" << endl;
  }else{
    cout << "Impossible" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int game(int player);
int pos[3] = {0,0,0};
string A[3];

int main(){
	cin >> A[0] >> A[1] >> A[2];
	cout << (char)(game(0)+65) << endl;
}

int game(int player){
	if(pos[player] >= A[player].length()) return player;
	return game(A[player][pos[player]++]-97);
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)

typedef long long ll;

ll vs[200000+10];
ll cs[200000+10];
map<ll, queue<int> > table;

int main(void) {
  int n;
  ll k;
  scanf("%d%lld", &n, &k);
  cs[0] = 0;
  REP(i, n) {
    scanf("%lld", &vs[i]);
    vs[i] = (vs[i] + k - 1) % k;
    cs[i+1] = (cs[i] + vs[i]) % k;
  }
  ll res = 0;
  // REP(i, n) {
  //   cerr << i << " : " << vs[i] << endl;
  // }
  // cerr << endl;
  // REP(i, n+1) {
  //   cerr << i << " : " << cs[i] << endl;
  // }
  for(int i = n; i >= 0; --i) {
    ll cur = cs[i];
    ll opp = cur;
    while(!table[opp].empty() && table[opp].front() >= i+k) {
      table[opp].pop();
    }
    // if(table[opp].size() > 0) {
    //   cerr << i << " " << table[opp].size() << endl;
    // }
    res += table[opp].size();
    table[cur].push(i);
  }
  cout << res << endl;

  return 0;
}


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

int main(){
  long i,N;
  long long ans=0;
  scanf("%ld",&N);
  for(i=1;i*i+i<N;i++){
    if(N%i==0){
      ans+=N/i-(long)(1);
    }
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney, tree, chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun

#define REP(i,a,b) for(int i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIY PRI("Yes")
#define PRIN PRI("No")


struct node {
	int id;
	vector<int> link;
	int state;
};
int N, M;
vector<node> nod;

void infection(int id, int v) {
	nod[id].state = v;
	for (int& ind : nod[id].link) {
		if (nod[ind].state == -1) infection(ind, v);
	}
}

int main() {
	cin >> N >> M;
	nod.resize(N);
	REP(i, 0, N) {
		nod[i].id = i;
		nod[i].state = -1;
	}
	REP(i, 0, M) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		nod[a].link.push_back(b);
		nod[b].link.push_back(a);
	}
	int cnt = 0;
	REP(i, 0, N) {
		if (nod[i].state == -1) {
			infection(i, cnt);
			++cnt;
		}
	}
	vector<int> cc;
	cc.resize(cnt, 0);
	REP(i, 0, N) cc[nod[i].state]++;
	int ans = 1;
	for (int& aaa : cc) ans = max(ans, aaa);
	PRI(ans);
	return 0;
}




Measured memory_bytes: 23432
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define RFOR(i, a, b) for(int i = a; i >= b; --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
const int INF = 1e9;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
int main() {
    int h, w;
    cin >> h >> w;
    string s[h];
    vector<vi> cnt(h, vi(w));
    REP(i, h) cin >> s[i];
    REP(i, h) {
        vi done(w);
        REP(j, w) {
            if(s[i][j] == '#') continue;
            if(done[j]) continue;
            int l = 0;
            while(j+l < w) {
                if(s[i][j+l] == '#') break;
                ++l;
            }
            REP(k, l) {
                cnt[i][j+k] += l;
                done[j+k] = 1;
            }
        }
    }
    REP(j, w) {
        vi done(h);
        REP(i, h) {
            if(s[i][j] == '#') continue;
            if(done[i]) continue;
            int l = 0;
            while(i+l < h) {
                if(s[i+l][j] == '#') break;
                ++l;
            }
            REP(k, l) {
                cnt[i+k][j] += l;
                done[i+k] = 1;
            }
        }
    }
    int ans = 0;
    REP(i, h) {
        REP(j, w) {
            ans = max(ans, cnt[i][j] - 1);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 20992
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

typedef long long ll;

using namespace std;
int main(){
    int N;
    cin >> N;

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

    int half = N / 2 + 1;;

    for (int i = N; i >= half; i--) {
    	b[i] = a[i];
    }

    for (int i = max(half - 1, 1); i >= 1; i--) {
    	int sum = 0;
    	for (int j = i * 2; j <= N; j += i) {
    		sum += b[j];
    	}
    	if (sum % 2 == a[i]) {
    		b[i] = 0;
    	}
    	else {
    		b[i] = 1;
    	}
    }

    int nonzero = 0;
    for (int i = 1; i <= N; i++) {
    	if (b[i] == 1) {
    		nonzero++;
    	}
    }

    if (nonzero == 0) {
    	cout << 0 << "\n";
    }
    else {
    	cout << nonzero << "\n";
    	for (int i = 1; i <= N; i++) {
    		if (b[i] == 1) cout << i << " ";
    	}
    }

}


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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vst = vector<st>;
using vchar = vector<char>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007;

int main(){
  ll n;
  cin >> n;
  vll a(n);
  vin(a);
  bool ans = true; 
  vrep(i, a) if(i % 2 == 0) if(i % 3 != 0 && i % 5 != 0) ans = false;
  cout << (ans ? "APPROVED" : "DENIED") << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define vv vector
#define pp pair
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define fastio                    \
	ios_base::sync_with_stdio(0); \
	cin.tie(0);
typedef pair<ll, ll> pll;
typedef vv<ll> vll;
typedef vv<pll> vpll;
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
//adds two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set]
//(2)set.order_of_key(k)[count of elements strictly less than k]
#define LG(args...)                               \
	{                                             \
		string _s = #args;                        \
		replace(_s.begin(), _s.end(), ',', ' ');  \
		stringstream _ss(_s);                     \
		err(istream_iterator<string>(_ss), args); \
		cerr << endl;                             \
	}
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << "(" << *it << ":" << a << ") ";
	err(++it, args...);
}
//:::::::::::::::::::::::::::::::::::::::::::::
const ll INF = 9e18;
const ll MOD = 1e9 + 7;
// #define dbg

#define wt ff
#define val ss

int main() {
	fastio;
	ll n, W;
	cin >> n >> W;
	vpll v(n);
	ll vmx = 0;
	for (auto& i : v) {
		cin >> i.wt >> i.val;
		vmx += i.val;
	}
	//for explanation see d.cpp
	//similar idea
	//dp[i] is minimum wt required to get val exact
	//i form allowed list
	//dp[i + val[i]] = min(self, dp[i] + wt[i])
	auto minself = [](ll & a, ll b) {
		a = min(a, b);
	};

	vll dp(vmx+1, INF);
	dp[0]=0;
	for (ll i = 0; i < n; i++) {
		for (ll j = vmx-v[i].val; j >= 0; j--) {
			minself(dp[j + v[i].val], dp[j] + v[i].wt);
		}
	}
	// ll ans = INF;
	for(ll i=vmx; i>=0; i--){
		// LG(i,dp[i])
	}
			
	ll ans=0;
	for(ll i=vmx; i>=0; i--){
		if(dp[i] <=W){
			ans = i;
			break;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 3924
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int a[1007];
int b[255555];
int c[255555];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=1005;i++)
    {

        a[i]=a[i-1]+i;
    }
int n,k;
cin>>n>>k;

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

    for(int i=1;i<=n;i++)
    {
       c[i]=c[i-1]+b[i];

    }
    ll max1=-1;
    ll index2=-1;
    int endx=k;
    for(int i=0;i<=n;i++)
    {

        if(c[endx]-c[i]>max1)
        {
            index2=i+1;
            max1=c[endx]-c[i];
        }
        endx++;
    }
    double sum=0;

    for(int i=index2;i<k+index2;i++)
    {
        int x;
        x=b[i];
        sum+=a[x]/double(x);

    }
    cout<<fixed<<setprecision(12)<<sum<<'\n';






}


Measured memory_bytes: 1792