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

typedef long long ll;
#define vec vector<int>
#define vecll vector<ll>
#define vpair vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n)   for(int i=(int)0; i<(int)n; i++)
#define llrep(i,n)   for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n) for(int i=(int)m; i<(int)n; i++)
#define all(var)     (var).begin(), (var).end()
#define prt(var)     cout << var << endl
#define prt_dbl(i,var) cout<<fixed<<setprecision(i)<<var<<endl;
template <typename Val,typename Number>
//use ll or int for gcd
Val gcd(Val a, Val b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}
//count vector and return pair (count,vector item)
template <typename Val,typename Number>
void count_vector(vector<Val>* A,vector<pair<Number,Val>>*R){
  sort(A->begin(),A->end());
  int count = 1;
  rep(i,A->size()){
    if(i<A->size()-1){
      if(A->at(i)==A->at(i+1))count++;
      else{
        R->push_back(make_pair(count,A->at(i)));
        count = 1;
      }
    }else{
      R->push_back(make_pair(count,A->at(i)));
      count = 1;
    }
  }
}

//---------------------------------------------------------------

int main(){
  int K,N,ans,dmax;
  cin>>K>>N;
  vec A(N);
  rep(i,N){
    cin>>A.at(i);
  }
  sort(A.begin(),A.end());
  ans = dmax = 0;
  rep(i,N-1){
    ans+=A.at(i+1)-A.at(i);
    dmax = (dmax<A.at(i+1)-A.at(i) ? A.at(i+1)-A.at(i):dmax);
  }
  int rasd = A.at(0)+(K-A.at(N-1));
  ans +=rasd;
  dmax = (dmax<rasd ? rasd:dmax);
  ans -=dmax;

  cout<<ans<<endl;




}


Measured memory_bytes: 1024
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  int a,b,c;
  cin >> a >> b >> c;

  cout << a * b / 2;  

  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 256
#include <stdio.h>
#define WHITE 0
#define GRAY 1
#define BLACK 2
int n;
int A[100][100];

int prim(){
  int u,minv;
  int d[100],p[100],color[100];
  int i,v;
  int sum = 0;

  for (i=0; i < n; i++){
    d[i] = 100000;
    p[i] = -1;
    color[i] = WHITE;
  }

  d[0] = 0;

  while(1){
    minv = 100000;
    u = -1;
    for(i = 0; i < n; i++){
      if(minv > d[i] && color[i] != BLACK){
	u = i;
	minv = d[i];
      }
    }

    if( u == -1 )break;
    color[u] = BLACK;
    for( v = 0; v < n; v++){
      if( color[v] != BLACK && A[u][v] != 100000 ){
	if( d[v] > A[u][v] ){
	  d[v] = A[u][v];
	  p[v] = u;
	  color[v] = GRAY;
	}
      }
    }
  }

  for(i = 0; i < n; i++){
    if( p[i] != -1) sum += A[i][p[i]];
  }
  return sum;
  
}
int main(){
  int i,j;
  int a;
  scanf("%d",&n);
    for(i=0; i<n; i++){
      for(j = 0; j<n ;j++){
	scanf("%d",&a);
	A[i][j] = (a == -1) ? 100000 : a;
      }
    }
  
  printf("%d\n",prim());
  
  return 0;
}



Measured memory_bytes: 2104
#define _GLIBCXX_DEBUG
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < int(n); ++i)

int partition(vector<int> &A, int p, int r) {
    int x = A.at(r);
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (A[j] <= x) {
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A.at(i + 1), A.at(r));
    return i + 1;
}

void solve() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (auto &e : A) {
        cin >> e;
    }
    int idx = partition(A, 0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        if (i == idx) {
            cout << "[" << A.at(i) << "]";
        } else {
            cout << A.at(i);
        }
    }
    cout << "\n";
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 3228
#include <bits/stdc++.h>
#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; }
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    deque<int> d;
    rep(i,n) {
        int p = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
        if(p == 0) {
            d.push_front(a[i]);
        }
        else d[p-1] = a[i];
    }
    cout << d.size() << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0), cin.tie(0) 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int inf = ~0u >> 1;
bool flag[105];
int main() {
    IO;
    int n, k;
    cin >> n >> k;
    int cnt = 0;
    while (k--) {
        int d;
        cin >> d;
        for (int i = 0; i < d; ++i) {
            int a;
            cin >> a;
            if (!flag[a])
                cnt++;
            flag[a] = true;
        }
    }
    cout << n - cnt << endl;
    return 0;
}

Measured memory_bytes: 3652
#include<stdio.h>
#define MAX 100000

int A[MAX], n;

int partition(int p, int r){
  int x, i, j, t;
  x = A[r];
  i = p-1;
  for(j=p; j<r;j++){
    if(A[j] <= x){
      i++;
      t = A[i];
      A[i] = A[j];
      A[j] = t;
    }
  }
  t= A[i+1];
  A[i+1] = A[r];
  A[r] = t;
  return i+1;
}
int main(){
  int i, q;

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

  q = partition(0, n-1);

  for(i=0;i<n;i++){
    if(i) printf(" ");
    if(i == q) printf("[");
    printf("%d", A[i]);
    if(i == q) printf("]");
  }
  printf("\n");

  return 0;
}




Measured memory_bytes: 2120
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public final class Main {

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final int n = in.nextInt();
        long k = in.nextLong();
        in.nextLine();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        in.nextLine();
        int slow = 1;
        int fast = 1;
        do {
            slow = arr[slow - 1];
            fast = arr[arr[fast - 1] - 1];
        } while (slow != fast);
        int cycle = 0;
        do {
            slow = arr[slow - 1];
            cycle++;
        } while (slow != fast);
        slow = 1;
        int initial = 0;
        while (slow != fast) {
            slow = arr[slow - 1];
            fast = arr[fast - 1];
            initial++;
        }
        if(k > initial) {
            k -= initial;
            k = Math.floorMod(k, cycle);
            int res;
            for (res = slow; k > 0; k--) {
                res = arr[res - 1];
            }
            System.out.println(res);
        } else {
            int res;
            for (res = 1; k > 0; k--) {
                res = arr[res - 1];
            }
            System.out.println(res);
        }
    }
}


Measured memory_bytes: 60104
l,r = map(int, input().split())
lst = []

lmod = l%2019
rmod = r%2019

if r-l>=2018:
    print(0)
elif lmod < rmod:
    for i in range(lmod, rmod+1):
        lst.append(i)
    ans = 2018
    for i in range(len(lst)):
        for j in range(i+1,len(lst)):
            ans = min(ans, (lst[i]*lst[j])%2019)
    print(ans)
else:
    print(0)


Measured memory_bytes: 3060
import sys
a=[1]*500000
for i in range(3,999,2):
 if a[i//2]:a[(i*i)//2::i]=[0]*len(a[(i*i)//2::i])
for e in map(int,sys.stdin):print([e-1,sum(a[:(e+1)//2])][e>3])


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

int *num;
int debug = 0;

void swap(int a, int b){
	int tmp;

	tmp = num[a];
	num[a] = num[b];
	num[b] = tmp;

	return;
}

int main(void){
	int n, m;
	int i;
	int a, b;

	scanf("%d", &n);
	scanf("%d", &m);
	if(debug) printf("n=%d, m=%d\n", n, m);

	num = (int *)malloc(sizeof(int) * (n+1));
	for(i=1;i<=n;i++){
		num[i] = i;
	}

	for(i=0;i<m;i++){
		scanf("%d,%d", &a, &b);
		swap(a, b);
	}

	for(i=1;i<=n;i++){
		printf("%d\n", num[i]);
	}

	if(debug) while(1);
	return;
}

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

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

int main()
{
	string a, b;

	cin >> a >> b;

	int len = (int)a.size() + (int)b.size();

	REP(i, len){
		if (i % 2) cout << b[i / 2];
		else cout << a[i / 2];

	}

	cout << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	int x[5];
	scanf("%d %d %d %d %d",&x[0],&x[1],&x[2],&x[3],&x[4]);
	for(int i=0;i<5;i++){
		if(x[i]==0){
			printf("%d",i+1);
			return 0;
		}
	}
}

Measured memory_bytes: 1732
#include <cstdio>
#include <cmath>
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <utility>

using namespace std;

int main () {
    int n,y;
    int cnt=0;
    int ti,tj;
    cin >> n >> y;
    int kane = 10000*n;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n-i;j++){
            if(y == kane - 5000*i -9000*j){
                cnt++;
                ti = i;
                tj = j;
            }
        }
    }
    if(cnt>0){
        printf("%d %d %d\n",n-ti-tj,ti,tj);
    }else{
        printf("-1 -1 -1\n");
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007;
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main(){
    int n,a,b;
    cin>>n>>a>>b;
    if(a*n>b){
        cout<<b<<endl;
    }
    else{
        cout<<a*n<<endl;
    }
}


Measured memory_bytes: 256
package main

import "fmt"

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a >= b {
		return b
	}
	return a
}

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)
	// タスク間の差の変化が最も少ないように並べると全体のコストが最小となる。
	// つまり Ax > Ay > Azとした場合、全体のコストは
	// (Ax - Ay) + (Ay - Az)となって、結果max(a,b,c)-min(a,b,c)となる。
	fmt.Println(max(a, max(b, c)) - min(a, min(b, c)))
}


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

using namespace std;

int main(int argc, const char *argv[]) {
  int n;
  string s;
  cin >> n >> s;

  vector<char> ans(n, '\0');
  auto solve = [&]() -> bool {
    bool ok = true;
    for (int i = 0; i < s.size() && ok; ++i) {
      int a = i != 0 ? i - 1 : s.size() - 1;
      int b = i != s.size() - 1 ? i + 1 : 0;
      if (a > b) {
        swap(a, b);
      }

      bool same =
          (ans[i] == 'S' && s[i] == 'o') || (ans[i] == 'W' && s[i] == 'x');
      char ans_b;
      if (same) {
        ans_b = ans[a];
      } else {
        ans_b = ans[a] == 'S' ? 'W' : 'S';
      }

      if (s.size() - i <= 2) {
        ok = ans[b] == ans_b;
      } else {
        ans[b] = ans_b;
      }
    }

    return ok;
  };

  vector<array<char, 2>> pat{{'S', 'S'}, {'W', 'W'}, {'S', 'W'}, {'W', 'S'}};
  for (auto p : pat) {
    fill(ans.begin(), ans.end(), '\0');
    ans[0] = p[0];
    ans[1] = p[1];

    if (solve()) {
      cout << string(ans.begin(), ans.end()) << '\n';
      return 0;
    }
  }

  cout << -1 << '\n';
  return 0;
}

Measured memory_bytes: 3820
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
  char mp[2][4];
  char cp[2][4];
  char c;
  int f=0;
  for(int i=0;i<2;i++){
    for(int j=0;j<3;j++){
      cin >> c;
      mp[i][j]=c;
      cp[1-i][2-j]=c;
    }
  }
  mp[0][3]='\0';
  mp[1][3]='\0';
  cp[0][3]='\0';
  cp[1][3]='\0';
  if(strcmp(mp[0],cp[0])==0&&strcmp(mp[1],cp[1])==0)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

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

int main() {
    int n;
    string s, t;
    cin >> n;
    cout << n - 1 << endl;
    cin >> s;
    if (s == "Vacant")
        return 0;
    cout << 0 << endl;
    cin >> s;
    if (s == "Vacant")
        return 0;
    int lo = 0, hi = n - 2, mid;
    while (1) {
        if (hi - lo == 1) {
            cout << lo << endl;
            cin >> s;
            if (s == "Vacant")
                return 0;
            cout << hi << endl;
            cin >> s;
            return 0;
        }
        mid = (lo + hi)/2;
        if ((hi - mid) % 2 == 0) mid++;
        cout << mid << endl;
        cin >> t;
        if (t == "Vacant")
            return 0;
        if (s == t)
            lo = mid;
        else
            hi = mid - 1;
    }
    return 0;
}


Measured memory_bytes: 852
SX,SY,TX,TY=map(int,input().split())
vx=TX-SX
vy=TY-SY
print('U'*vy+'R'*vx+'D'*vy+'L'*vx+'L'+'U'*(vy+1)+'R'*(vx+1)+'D'+ 'R'+'D'*(vy+1)+'L'*(vx+1)+'U')

Measured memory_bytes: 9112
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
#define MAX_N 1000100
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
 
ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    ll a,b;
    cin >> a >> b;
    
    if (a > 8 || b > 8)cout << ":(" << endl;
    else cout << "Yay!" << endl;
    
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <map>

#define MAX_LEN 11
typedef long long ll;
typedef std::map<ll, int> Map;

/* -----------------------------------------------------------------------------
	大域データ
----------------------------------------------------------------------------- */
int N;	// 文字列の個数の個数(1≦N≦10^5)
Map m;	// 連想コンテナ()
char s[MAX_LEN];

ll atoll(char *s) {
	
	char alph[26] = {0};
	ll   n = 0;
	// 文字の出現頻度
	for(int i = 0; i < 10; i++) alph[s[i] - 'a']++;
	// 符号化(encode)
	for(int i = 0; i < 26; i++)
		n = 26 * n + alph[i];

	return n;
}


int main () {
	// 文字列数の読込み
	scanf("%d", &N);
	// 符号化してマップへ格納，個数を数える
	for(int i = 0; i < N; i++) {
		scanf("%s", s);
		ll n = atoll(s);

		if(m.find(n) == m.end())
			m[n] = 1;
		else
			m[n] ++;
	}

	// 組合せを計算する
	ll cnt = 0;
	for(auto v : m) {
		//printf(">%d\n", v.second);
		cnt += (ll)v.second * (v.second - 1) / 2;
	}
	printf("%lld\n", cnt);	

	return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<vector>
#include<cmath>
#include<utility>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
int main(void) {
	int n; cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	ll tmpsum = 0,sum=1000000000;
	for (int i = -100; i <= 100; i++) {
		for (int wi = 0; wi < n; wi++) {
			tmpsum += pow(v[wi] - i,2);
		}
		if (tmpsum <= sum) {
			sum = tmpsum;
			tmpsum = 0;
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]

INF = 1 << 30
mx = INF
sm = 0
for i in range(n):
    a, b = ab[i]
    sm += a
    if a > b:
        mx = min(mx, b)
if mx == INF:
    print(0)
else:
    print(sm - mx)


Measured memory_bytes: 11516
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

int main()
{
	string S;
	cin >> S;

	for (int i = 0; i < S.length() - 1; i++) {
		if (S[i] == 'A' && S[i + 1] == 'C') {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;

}


Measured memory_bytes: 3536
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static System.Array;

class Program
{
    public static void Main()
    {
        var n = ReadLine();
        if(n == "ABC")
        {
            WriteLine("ARC");
        }
        else
        {
            WriteLine("ABC");
        }
    }
}


Measured memory_bytes: 17356
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <cassert>
#include <iomanip>

using namespace std;

#define dump(x)  cout << " "<< #x << " = " << (x) << endl;
#define pb push_back
typedef long long ll;
typedef complex<int> P;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INF = 1e+6;


struct st{
	int a, b;
	int d;
	st(){}
};


int prim(vector<bool>& used, vector<int>& mincost, vector<vector<int> >& cost, int V){
	for(int i=0;i<V;i++){
		mincost[i] = INF;
		used[i] = false;
	}
	mincost[0] = 0;
	int res = 0;
	while(true){
		int v = -1;
		for(int u=0;u<V;u++){
			if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
		}
		if(v == -1) break;
		used[v] = true;
		res += mincost[v];
		for(int u=0;u<V;u++){
			mincost[u] = min(mincost[u], cost[u][v]);
		}
	}
	return res;
}

bool solve(){
	int n;
	cin>> n;
	if(!n) return false;
	
	int m;
	cin>> m;
	vector<st> vst(m);
	for(int i=0;i<m;i++){
		char c1, c2;
		cin>> vst[i].a>> c1>> vst[i].b>> c2>> vst[i].d;
		vst[i].d = vst[i].d/100 -1;
	}

	vector<bool> used(m, false);
	vector<int> mincost(n, INF);
	vector<vector<int> > cost(n, vector<int>(n, INF));
	for(int i=0;i<m;i++){
		int u = vst[i].a;
		int v = vst[i].b;
		int c = vst[i].d;
		cost[u][v] = c;
		cost[v][u] = c;
	}
	
	cout<< prim(used, mincost, cost, n)<< endl;
	return true;
}

int main(){
	cout.setf(ios::fixed);
	cout.precision(10);
	
	while(solve());
	return 0;
}

 

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

#define forn(i,n) for (int i = 0; i < int(n); i++)

const int N = 222;
const int INF = N+2;

int n, d[N][N];

int bip = 1, col[N];
void paint(int u, int c) {
    if (col[u]) {
        if (col[u] != c) bip = 0;
        return;
    }
    col[u] = c;
    forn(v,n) if (d[u][v] == 1) {
        paint(v, 3-c);
    }
}

int main() {
    cin >> n;
    forn(i,n) {
        string s; cin >> s;
        forn(j,n) d[i][j] = (s[j] == '0' ? INF : 1);
        d[i][i] = 0;
    }
    forn(i,n) if (!col[i]) paint(i,1);
    if (!bip) return cout << -1, 0;

    forn(k,n) forn(i,n) forn(j,n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    map<int,int> max_d;
    forn(i,n) {
        int cls = -1, md = 0;
        forn(j,n) if (d[i][j] < INF) {
            cls = j;
            md = max(md, d[i][j]);
        }
        max_d[cls] = max(max_d[cls], md);
    }
    long long result = 0;
    for (auto xy : max_d) {
        result += xy.second+1;
    }
    cout << result << endl;

    return 0;
}


Measured memory_bytes: 384
#include<iostream>

using namespace std;

int main() {
	int H1, M1, H2, M2, K;
	cin >> H1 >> M1 >> H2 >> M2 >> K;


	int total_min = 0;
	if (M2 >= M1) {
		total_min = (H2 - H1) * 60 + (M2 - M1);
	}
	else {
		total_min = (H2 - H1) * 60 - (M1 - M2);
	}

	cout << total_min - K << endl;

}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ldb = long double;
using pa = pair < ll, ll >;
using vec = vector < ll >;
#define pb push_back
#define po pop_back
#define mp make_pair
#define mt make_tuple
#define F  first
#define S  second
#define f(i,x,n) for(ll i=x;i<n;i++) 
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))
#define all(c) c.begin(),c.end()
#define str string
#define edl "\n"
#define add insert
#define cot continue
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
const int MOD = 1e9 + 7, INF = INT_MAX, N = 1e5 + 10;
const double PI = acos(-1);
const ll LINF = LLONG_MAX;




int main() 
{

 fast();
  
  // #ifndef ONLINE_JUDGE
  //   freopen("input.txt", "r", stdin);
  //   freopen("output.txt","w",stdout);
  // #endif
  
 str s;
  cin>>s;
  f(i,1,4)
  {
    if(s[i]==s[i-1])
    {
      cout<<"Bad";
      return 0;
    } 	
  }
  cout<<"Good";

  


    




    cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
    return 0;


} 


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include <cmath>

using namespace std;

int H,W,N,X,ans;

int main()
{
  cin>>H>>W>>N;
  
  X=max(H,W);
  
  if(N%X==0)  ans=N/X;
  else ans=N/X+1;
  
  cout << ans;
  
  
}

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

int main() {
    int N; cin >> N;
    ll a[100];
    a[0] = 2, a[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        a[i] = a[i-1] + a[i-2];
    }
    cout << a[N] << endl;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    T = list(map(int, input().split()))
    M = int(input())
    t_sum = sum(T)
    ans = []
    for i in range(M):
        p, x = map(int, input().split())
        ans.append(t_sum - T[p - 1] + x)
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
n,m = map(int, input().split())

a = [0] * m

for i in range(m):
    a[i] = tuple(map(int, input().split()))

a.sort(reverse=True)

c = n + 1
ret = 0
for i in range(m):
    lft, rgt = a[i]
    if rgt <= c:
        c = lft
        ret += 1

print(ret)

Measured memory_bytes: 16972
#include<bits/stdc++.h>
  using namespace std;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define endl "\n"
  #define all(v) v.begin(),v.end()
  #define f first
  #define s second
  #define PB push_back
  #define MP make_pair
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
  #define MOD 998244353
  #define N 100005
  #define INF 1000000000000
  #define eps 1e-6
  #define int long long

int32_t main()
{


    int n,k;
    cin >>n >> k;


    int ans = n*(n-1)/2 - k;

    if(ans < n - 1)
    {
      cout << -1;
      return 0;
    }

    cout << ans << endl;

    for(int i = 1; i <= n; i++)
    {
      for(int j = i + 1; j <= n; j++)
      {
        cout << i << " " << j << endl;
        ans--;
        if(ans == 0)return 0;
      }
    }



    return 0;
}


Measured memory_bytes: 256
#ifndef ___Class_RMQ
#define ___Class_RMQ

#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

template <typename Type> class RMQ
{
private:

	int size;

	vector<Type> minvalue;
	vector<Type> maxvalue;

	pair<Type, Type> _query(int a, int b, int k, int l, int r)
	{
		if (r <= a || b <= l) { return make_pair(INF, -INF); }
		if (a <= l && r <= b) { return make_pair(minvalue[k], maxvalue[k]); }

		pair<Type, Type> vl = _query(a, b, 2 * k + 1, l, (l + r) / 2);
		pair<Type, Type> vr = _query(a, b, 2 * k + 2, (l + r) / 2, r);

		return make_pair(min(vl.first, vr.first), max(vl.second, vr.second));
	}

public:

	Type INF;

	RMQ(int size_)
	{
		INF = numeric_limits<Type>::max();

		for (size = 1; size < size_;) { size <<= 1; }

		minvalue = vector<Type>(size * 2 - 1, INF);
		maxvalue = vector<Type>(size * 2 - 1, -INF);
	}

	void update(int i, const Type& x)
	{
		i += size - 1;

		minvalue[i] = x;
		maxvalue[i] = x;

		while (i > 0)
		{
			i = (i - 1) / 2;

			minvalue[i] = min(minvalue[2 * i + 1], minvalue[2 * i + 2]);
			maxvalue[i] = max(maxvalue[2 * i + 1], maxvalue[2 * i + 2]);
		}
	}

	pair<Type, Type> query(int s, int t)
	{
		return _query(s, t, 0, 0, size);
	}
};

#endif


// ------ main ------ //

#include <cstdio>

using namespace std;

int n, q, com, x, y;

int main()
{
	scanf("%d", &n);
	scanf("%d", &q);

	RMQ<int> r(n);

	for (int i = 0; i < q; i++)
	{
		scanf("%d", &com);
		scanf("%d", &x);
		scanf("%d", &y);

		if (com == 0) 
		{
			r.update(x, y);
		}
		if (com == 1) 
		{
			pair<int, int> p = r.query(x, y + 1);

			printf("%lld\n", p.first != r.INF ? p.first : (1LL << 31) - 1);
		}
	}

	return 0;
}

Measured memory_bytes: 4504
import java.util.*;
    public class Main {
     
    	public static void main(String[] args) {
    		Scanner scan=new Scanner(System.in);
    		int a=Integer.parseInt(scan.next());
    		int b=Integer.parseInt(scan.next());
    		int h=Integer.parseInt(scan.next());
    		System.out.print((a+b)*h/2);
    }
     
    }

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

int main() {
    int n, rating, temp = 0;
    cin >> n;
    set<int> color;
    rep(i, n) {
        cin >> rating;
        if(rating >= 3200) {
            temp++;
            continue;
        }
        color.insert(rating / 400);
    }
    int m = color.size();
    cout << max(m, 1) << " " << m + temp << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
using ll=long long;
#define rep(i,a,b) for(ll i=a;i<ll(b);i++)
#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)
#define endl "\n"
#define ALL(x) x.begin(),x.end()
#define ALLR(x) x.rbegin(),x.rend()
using namespace std;

int N;
int main() {
	cin >> N;
	vector<int> A(N);
	rep(i, 0, N) cin >> A[i];

	sort(ALLR(A));

	ll ans = A[0];
	int t = N-2, i = 1;
	while(1){
		if(t <= 0) break;
		ans += A[i]; t--;
		if(t <= 0) break;
		ans += A[i]; t--;
		i++;
	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3612
import java.util.Scanner
import scala.collection.Searching._

import scala.annotation.tailrec

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  @tailrec
  private def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {
  def solve(sc: => Scanner): Unit = {
    val T = sc.nextInt
    for (_ <- 0 until T) {
      val N, K = sc.nextInt
      val A = Array.fill(N)(sc.nextInt)
      for (i <- 0 until N - 1) {
        A(i) = A(i + 1) - A(i)
      }
      A(N - 1) = 10000000
      val C = A.sorted
      var ans = 0
      for (i <- 0 until N - K) {
        ans += C(i)
      }
      println(ans)
    }
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)

    solve(sc)
  }
}

Measured memory_bytes: 320400
n,m=map(int,input().split())
h=list(map(int,input().split()))
tennbou=[1]*n
for i in range(m):
  a,b=map(int,input().split())
  if h[a-1]>h[b-1]:
    tennbou[b-1]=0
  elif h[a-1]<h[b-1]:
    tennbou[a-1]=0
  elif h[a-1]==h[b-1]:
    tennbou[a-1]=0
    tennbou[b-1]=0
  
print(tennbou.count(1))

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

int n;
int a[100010];
long bit[100010];

long sum(int i){
  long sum = 0;
  while(i > 0){
    sum += bit[i];
    i -= i & -i;
  }
  return sum;
}

void add(int i, long x){
  while(i <= n+1){
    bit[i] += x;
    i += i & -i;
  }
}

long iinv(int s[]){
  vector<int> t(n+1);
  rep(i, n+1) t[i] = s[i];
  sort(t.begin(), t.end());
  t.erase(unique(t.begin(), t.end()), t.end());
  map<int, int> m;
  rep(i, t.size()) m[t[i]] = i+1;
  rep(i, n+1) s[i] = m[s[i]];
  rep(i, n+2) bit[i] = 0;
  long ans = 0;
  rep(i, n+1){
    ans += sum(s[i]);
    add(s[i], 1);
  }
  return ans;
}   

bool check(int mid){
  int s[n+1];
  s[0] = 0;
  rep(i, n){
    int t;
    if(a[i] < mid) t = -1;
    else t = 1;
    s[i+1] = s[i] + t;
  }
  long k = n;
  return iinv(s) >= ((k+1)*k/2 - 1) / 2 + 1;
}

int main(){
  cin >> n;
  rep(i, n) cin >> a[i];
  int ok = 0;
  int ng = 1000000001;
  while(ng-ok > 1){
    int mid = (ok+ng) / 2;
    if(check(mid)) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
}

Measured memory_bytes: 9024
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
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; }
//ミョ(-ω- ?)
int main() {
    vector<int> a(5);
    rep(i,5)cin >> a[i];
    rep(i,5){
        if(a[i] == 0){
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3628
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>

#if __cplusplus >= 201103 //C++11~
#include <tuple>

#endif

using namespace std;

typedef pair<int,int> Paint;

bool Pairsecond(const Paint& pf,Paint&ps){//sortCompare
  return pf.second < ps.second;
}

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)
#define pb push_back
#define MAX 1000000000
#define MOD 1000000007

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")

int main(){
  int n,p;cin>>n>>p;
  vector<int> a(n);
  for(int i = 0; n > i; i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end(),greater<int>());

  for(int i = 0; n > i; i++){
    if(p > a[i]){
      cout << i << endl;
      return 0;
    }
  }
  cout << n << endl;
}

Measured memory_bytes: 640
N = int(input())
W = [int(i) for i in input().split()]

total = sum(W)
min_value = float('inf')
left = W[0]

for i in range(1, N):
    right = total - left
    dif = abs(left - right)
    min_value = min(min_value, dif)
    left += W[i]

print(min_value)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define VAL 100000
#define ll long long
#define INF 10000000000000000LL
#define pll pair<long long , long long>
const int MAX=1e4+10;
const ll MOD=1e9+7;
const int TOT_PRIMES=19;
const int MAX_A=70;
using namespace std;
int D;
ll dp[MAX][300][3];
int n;
string K;
bool vis[MAX][300][3];

int main() 
{ 
	//ios_base::sync_with_stdio(false);
  //  cin.tie(NULL);	
//	#ifndef ONLINE_JUDGE
//	freopen("inp.txt" ,"r", stdin );
//	freopen("out.txt", "w", stdout);
//	#endif
	cin>>K;
	cin>>D;
	n=K.size();
	dp[0][0][0]=1;
	for(int i=0;i<n;i++){
		int a=K[i]-'0';
		for(int j=0;j<D;j++){
			for(int x=0;x<10;x++){
				dp[i+1][(j+x)%D][1]+=dp[i][j][1];
				if(x==a){
					dp[i+1][(j+x)%D][0]+=dp[i][j][0];
				}
				else if(x<a){
					dp[i+1][(j+x)%D][1]+=dp[i][j][0];
				}
				dp[i+1][(j+x)%D][0]%=MOD;
				dp[i+1][(j+x)%D][1]%=MOD;
			}
		}
	}
	cout<<(dp[n][0][0]+dp[n][0][1]-1+MOD)%MOD;
	
}

Measured memory_bytes: 71040
using System;

class Program
{
    static void Main(string[] args)
    {
        var R = 8;
        var n = int.Parse(Console.ReadLine());

        var d = new bool[R];
        var over = 0;

        var s = Console.ReadLine().Split(' ');
        for (int i = 0; i < n; i++)
        {
            var x = int.Parse(s[i]) / 400;
            if (x < R) d[x] = true;
            else over++;
        }

        var a = 0;
        for (int i = 0; i < R; i++)
        {
            if (d[i]) a++;
        }

        if (0 < a)
        {
            Console.WriteLine($"{a} {a + over}");
        }
        else
        {
            Console.WriteLine($"1 {over}");
        }
    }
}


Measured memory_bytes: 13140
import std.stdio, std.conv, std.string, std.array, std.math, std.regex, std.range, std.ascii;
import std.typecons, std.functional;
import std.algorithm, std.container;

void scanLine(TList...)(ref TList list)
{
    auto elem = readln.split;
    foreach (i, T; TList)
    {
        list[i] = elem[i].to!T;
    }
}

T[] scanArray(T = long)()
{
    return readln.split.to!(T[]);
}

T scanElem(T = long)()
{
    string res;
    int c = ' ';
    while (isWhite(c) && c!=-1)
    {
        c = getchar;
    }
    while (!isWhite(c) && c!=-1)
    {
        res ~= cast(char)c;
        c = getchar;
    }
    return res.strip.to!T;
}

struct Sushi
{
    long t;
    long d;
}

template fold(fun...)
if (fun.length >= 1)
{
    auto fold(R, S...)(R r, S seed)
    {
        static if (S.length < 2)
        {
            return reduce!fun(seed, r);
        }
        else
        {
            import std.typecons : tuple;
            return reduce!fun(tuple(seed), r);
        }
    }
}

void main()
{
    const N = scanElem;
    const K = scanElem;
    Sushi[] sushies;
    foreach(i; 0..N)
    {
        Sushi sushi;
        scanLine(sushi.t, sushi.d);
        sushies ~= sushi;
    }
    sushies.sort!"a.d>b.d";

    auto eatTypes = sushies.take(K).map!"a.t".array.sort.group.assocArray;
    auto eatTypeCount = sushies.take(K).map!"a.t".array.sort.group.count;
    long eatPoint = sushies.take(K).fold!"a+b.d"(0L);
    long maxPoint = eatPoint+eatTypeCount^^2;
    auto eatHeap = BinaryHeap!(Sushi[], "a.d>b.d")(sushies.take(K));
    foreach(sushi; sushies.drop(K))
    {
        if(sushi.t in eatTypes)
            continue;
        while(!eatHeap.empty && eatTypes[eatHeap.front.t]==1)
        {
            eatHeap.popFront;
        }
        if(eatHeap.empty)
            break;
        auto removeSushi = eatHeap.front; eatHeap.popFront;
        eatHeap.insert(sushi);
        eatTypeCount++;
        eatTypes[sushi.t] = 1;
        eatTypes[removeSushi.t]--;
        eatPoint = eatPoint - removeSushi.d + sushi.d;
        maxPoint = max(maxPoint, eatPoint + eatTypeCount^^2);
    }
    writeln(maxPoint);
}


Measured memory_bytes: 10372
/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

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

#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)(x.size()))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     makep           make_pair
#define     maket           make_tuple
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)+(x)-1)/(x))
#define     gcd(a,b)        (__gcd((a),(b)))
#define     lcm(a,b)        ((a)*((b)/gcd((a),(b))))
#define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
#define     flush           fflush(stdout)
#define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ld pi=acos(-1);
const ll inf=1e10,M=1e9+7;
const int N=1;

void solve()
{
    int n,a,b;
    cin>>n>>a>>b;

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

    int beg=1,en=inf;
    int mid,ans;
    int cnt,tmp,d=a-b;
    while(beg<=en)
    {
        mid=(beg+en)/2;

        cnt=0;
        for(int i=0;i<n;++i)
        {
            tmp=v[i]-b*mid;
            if(tmp>0)
                cnt+=(tmp+d-1)/d;
        }

        if(cnt<=mid)
        {
            ans=mid;
            en=mid-1;
        }
        else
            beg=mid+1;
    }

    cout<<ans;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

int main(){
    ll n;cin>>n;
    string s;cin>>s;
    vi dp(n);
    dp[0]=1;
    rep(i,n-1){
        vi ndp(n);
        if(s[i]=='<'){
            ll sum=0;
            rep(j,i+2){
                ndp[j]=sum%mod;
                sum+=dp[j];
            }
        }
        else{
            ll sum=0;
            for(int j=i+1;j>=0;j--){
                sum+=dp[j];
                ndp[j]=sum%mod;
            }
        }
        dp=ndp;
    }
    ll ans=0;
    rep(i,n)ans+=dp[i];
    out(ans%mod);
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int main(){
    int n;
    cin >> n;
    map<int,int> m;
    rep(i,n){
        int b;
        cin >> b;
        if(b!=0) m[b-1]++;
        m[b+1]++;
        m[b]++;
    }
    int ans = -INF;
    for(auto t : m){
        if(ans<t.second){
            ans = t.second;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4736
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(ll i=a;i<b;++i)
#define rep(...) _overload3(__VA_ARGS__,_repi,_rep)(__VA_ARGS__)
#define _rrepi(i,a,b) for(ll i=b-1;i>=a;i--)
#define _rrep(i,n) _rrepi(i,0,n)
#define rrep(...) _overload3(__VA_ARGS__,_rrepi,_rrep)(__VA_ARGS__)
#define sum(...) accumulate(range(__VA_ARGS__),0)
#define _range(i) (i).begin(),(i).end()
#define _rangek(i,k) (i).begin(),(i).begin()+k
#define range(...) _overload3(__VA_ARGS__,a,_rangek,_range)(__VA_ARGS__)
#define LINF (ll)1000000000000000000
#define MOD (ll)1000000007
#define INF (int)1000000007
#define Yes(i) out(i?"Yes":"No")
#define YES(i) out(i?"YES":"NO")
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,size) vector<type> name(size);
#define VEC(type,name,size) vector<type> name(size);in(name)
struct aaa{aaa(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}aaaaaaa;
inline void in() {}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec);
template<typename T,typename L>
istream& operator >> (istream& is, pair<T,L>& p);
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec);
template<typename T,typename L>
ostream& operator << (ostream& os, pair<T,L>& p);
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;}
template<typename T,typename L>
istream& operator >> (istream& is, pair<T,L>& p){is >> p.first;is >> p.second;return is;}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;}
template<typename T,typename L>
ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;}
template <class Head, class... Tail>
inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);}
template <class T>
inline void out(T t){cout<<t<<'\n';}
template <class Head, class... Tail>
inline void out(Head head,Tail... tail){cout<<head<<' ';out(move(tail)...);}


int main(){
    INT(a,b,c);
    out((a+b)*c/2);
}














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

void input()
{ 
    #ifndef ONLINE_JUDGE 
    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    #endif
}
#define endl "\n"
#define ll long long int
#define vll vector<ll>
#define pb push_back
#define pll pair<ll,ll>
#define mp make_pair
#define ff first
#define ss second
#define tll tuple<ll,ll,ll>
#define mt make_tuple
#define INF LONG_LONG_MAX
#define mod 1000000007
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define cases ll t; cin>>t; while(t--)
#define array(a,n) ll a[n]; rep(i,0,n) cin>>a[i];
#define vector(a,n) vll a(n); rep(i,0,n) cin>>a[i];
#define sortall(a) sort(a.begin(),a.end())
#define printall(a,n) rep(i,0,n) cout<<a[i]<<" "; cout<<endl;

// --------------- My Template End --------------- //
double arr[2999+1]={},j=0;
map<string,double>dp;
int main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
   	//input();
   	int n;
   	cin>>n;
   	double sum=0;
   	rep(i,1,n+1)
   	{
   		cin>>arr[i];

   	}
   	double dp[n+1][n+1];
   	rep(i,0,n+1)
   	{
   		rep(head,0,n+1)
   		{
   			if(i==0)
   				dp[i][head]=1;
   			else if(head>i)dp[i][head]=0;

   			else if(head==0)
   			{
   				dp[i][head]=(1-arr[i])*dp[i-1][head];
   			}
   			else if(head==i)
   			{
   				dp[i][head]=arr[i]*dp[i-1][head-1];
   			}
   			else
   			{
   				dp[i][head]=arr[i]*dp[i-1][head-1]+(1-arr[i])*dp[i-1][head];
   			}
   			//cout<<dp[i][head]<<" ";

   		}
   		//cout<<endl;
   	}
   	rep(i,(n+1)/2,n+1)
   	{
   		sum+=dp[n][i];
   	}
   
    printf("%0.10f",sum);
}

 

Measured memory_bytes: 70656
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <random>

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

using namespace std;
typedef long long int ll;
const int INF = 1000000000;
const double PI = acos(-1);
const ll mod = 1000000007;

int main()
{
    int n;
    cin >> n;
    int ans = 1000 - (n % 1000);
    if (ans == 1000) ans = 0;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

int N;
string S;

int main() {
    cin >> N;
    bool even = N % 2;
    stack<int> s;
    queue<int> q;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        if (even ^ i % 2) {
            s.push(a);
        } else {
            q.push(a);
        }
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

Measured memory_bytes: 2944