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

void dfs(int u, int p, vector<vector<int>>& tree, vector<int>& dist) {
    for (int v : tree[u]) {
        if (v == p)
            continue;
        dist[v] = dist[u] + 1;
        dfs(v, u, tree, dist);
    }
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> tree(N + 1, vector<int>());
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    vector<int> dist(N + 1, 0);
    dfs(1, -1, tree, dist);

    vector<int> even, odd;
    for (int i = 1; i <= N; i++) {
        if (dist[i] % 2 == 0) {
            even.push_back(i);
        } else {
            odd.push_back(i);
        }
    }

    vector<int> p(N + 1, 0);
    vector<bool> used(N + 1, false);
    vector<queue<int>> r(3);
    for (int i = 1; i <= N; i++) {
        r[i % 3].push(i);
    }
    int E = even.size(), Od = odd.size();
    if (E <= (int)r[0].size()) {
        for (int v : even) {
            p[v] = r[0].front();
            used[p[v]] = true;
            r[0].pop();
        }
    } else if (Od <= (int)r[0].size()) {
        for (int v : odd) {
            p[v] = r[0].front();
            used[p[v]] = true;
            r[0].pop();
        }
    } else {
        for (int v : even) {
            if (!r[1].empty()) {
                p[v] = r[1].front();
                r[1].pop();
            } else {
                p[v] = r[0].front();
                r[0].pop();
            }
            used[p[v]] = true;
        }
        for (int v : odd) {
            if (!r[2].empty()) {
                p[v] = r[2].front();
                r[2].pop();
            } else {
                p[v] = r[0].front();
                r[0].pop();
            }
            used[p[v]] = true;
        }
    }

    queue<int> que;
    for (int i = 1; i <= N; i++) {
        if (!used[i]) {
            que.push(i);
        }
    }
    for (int i = 1; i <= N; i++) {
        if (p[i] == 0) {
            p[i] = que.front();
            que.pop();
        }
    }

    for (int i = 1; i <= N; i++) {
        cout << p[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 23924
import java.util.Scanner;
import java.lang.String;
public class Main{
	public static void main(String [] args){
    Scanner sc= new Scanner(System.in);
    String str1= sc.next();
    if(str1.endsWith("s"))
    {
    str1=str1+"es";
    }
    else
    {
    str1=str1+"s";
    }
    System.out.println(str1);
    }
}

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

typedef long long ll;
typedef long long int lli;
const int MOD = 1000000007;
#define rep(i,n) for (int i = 0; i < (n); i++)

using namespace std;

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

	int N; cin >> N;
	vector<int> ver(N);
	rep(i, N) { cin >> ver[i]; }
	vector<int> S(N);
	S = ver;
	sort(S.begin(), S.end());

	if (ver == S) {
		cout << "YES" << endl;
		return 0;
	}

	vector<int> NN(N);
	NN = ver;
	rep(x,N){
		rep(y, N) {
			int A = ver[x];
			NN[x] = ver[y];
			NN[y] = A;

			if (NN==S) {
				cout << "YES" << endl;
				return 0;
			}
			NN = ver;
		}
	}
	cout << "NO" << endl;
}


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

main(){
  int N,*a,i,count=0;
  scanf("%d",&N);
  a = malloc(sizeof(int)*N);
  for(i=0; i<N; i++){
    scanf("%d",&a[i]);
    while(a[i]%2==0){
      count++;
      a[i] /= 2;
    }
  }
  printf("%d\n",count);
}

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

int main()
{
    int N;
    string t;
    map<string, int> D;
    int res = 0;

    cin >> N;
    rep(i, N)
    {
        cin >> t;
        //cout << D[t] << endl;
        D[t] = D[t] + 1;
    }

    //int res = 0;
    int value;
    string key;

    auto begin = D.begin(), end = D.end();
    for (auto iter = begin; iter != end; iter++)
    {
        // first: key, second: value
        key = iter->first;
        value = iter->second;
        //cout << "value = " << iter->second << endl;
        //if (res > value)
        //    break;
        //res = value;
        //cout << key << endl;
        //cout << value << endl;
        if(res <= value)
            res = value;
        //res = iter->second;
    }
    //cout << endl;
    for (auto iter = begin; iter != end; iter++)
    {
        // first: key, second: value
        key = iter->first;
        value = iter->second;
        //cout << "value = " << iter->second << endl;
        //if (res > value)
        //    break;
        //res = value;
        //cout << key << endl;
        //cout << value << endl;
        if(res == value)
            cout << key << endl;
        //res = iter->second;
    }

    //cout << ((res) ? "APPROVED" : "DENIED");

    return 0;
}


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

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int cnt = 0;
    long long sum = 0;
    long long minv = LLONG_MAX;
    for (size_t i = 0; i < n; ++i) {
        long long a; cin >> a;
        cnt += (a < 0);
        sum += abs(a);
        minv = min(minv, abs(a));
    }
    if (cnt % 2) {
        sum -= 2 * minv;
    }
    cout << sum << "\n";
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int age = sc.nextInt();
        sc.close();
        if(age == 3 || age == 5 || age == 7){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }

}


Measured memory_bytes: 21972
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static PrintWriter pw = new PrintWriter(System.out);
    public static String line;
    public static StringTokenizer st;
    public static ArrayList<ArrayList<Integer>> adjList;
    public static int[] dx = {-1, 0, 1, 0, -1, 1, 1, -1};
    public static int[] dy = {0, 1, 0, -1, 1, 1, -1, -1};
    public static int INF = 0x3f3f3f3f;
    public static long LINF = 0x3f3f3f3f3f3f3f3fL;
    public static int MOD = 1000000007;

    public static long[][] memo;
    public static int N, P;
    public static int[] A;

    public static long solve(int index, int rem){
        if(index == N) return (rem == P) ? 1 : 0;
        if(memo[index][rem] != -1) return memo[index][rem];
        long total = solve(index+1, (rem + A[index]) % 2);
        total += solve(index+1, rem);

        return memo[index][rem] = total;
    }

    public static void main(String[] args) throws Exception{
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        memo = new long[N][2];
        for(int i = 0; i < N; i++){
            Arrays.fill(memo[i], -1);
        }

        pw.print(solve(0, 0) + "\n");

        pw.close(); 
        br.close();
    }
}

Measured memory_bytes: 22612
#include<cstdio>
#include<iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    int h[n];
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    int ans = 0;
    for(int i = 1; i <= 100; i++){
        bool flag = false;
        for(int j = 0; j < n; j++){
            if (h[j] >= i && !flag) {
                flag = true;
                ans++;
            }
            if (h[j] < i && flag) {
                flag = false;
            }
        }
    }
    
    cout << ans << '\n'; 
}

Measured memory_bytes: 256
room = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]

n = int(input())
for i in range(n):
  b,f,r,v = map(int,input().split())
  room[b-1][f-1][r-1] += v

sep = "#"*20

for i in range(4):
  for j in range(3):
    print(" {0} {1} {2} {3} {4} {5} {6} {7} {8} {9}".format(room[i][j][0],room[i][j][1],room[i][j][2],room[i][j][3],room[i][j][4],room[i][j][5],room[i][j][6],room[i][j][7],room[i][j][8],room[i][j][9]))
  if i < 3:
    print(sep)


Measured memory_bytes: 5620
#include <bits/stdc++.h>
#include <stdio.h>
 
using namespace std;
 
#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(i, a) for (auto &i: (a))
#define sz(x) (int)(x).size()
#define all(v) (v).begin(), (v).end()
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)

void solve();

signed main () {
    clock_t beg = clock();
    cout << fixed << setprecision(15);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    #endif 
    int t = 1; 
    // cin >> t;    
    int tt = t;
    while (t--) {
        // cout << "Case #" << tt - t << ": "; 
        solve();
    }
    cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
    return 0;
}
int dp[3005][3005] = {{0}};
const int M = 998244353;
void solve() {
    int a, b, c, d; 
    cin >> a >> b >> c >> d;
    dp[a][b] = 1;
    for (int rows = a; rows <= c; ++rows) {
        for (int cols = b; cols <= d; ++cols) {
            if (rows == a and cols == b)
                continue;
            if (rows - 1 >= a)
                dp[rows][cols] += dp[rows - 1][cols] * cols;
            if (cols - 1 >= b)
                dp[rows][cols] += dp[rows][cols - 1] * rows;
            if (rows - 1 >= a and cols - 1 >= b)
                dp[rows][cols] += (M - (dp[rows - 1][cols - 1] * (rows - 1) * (cols - 1)) % M) % M;
            dp[rows][cols] %= M;
        }
    }
    cout << dp[c][d];
}       

Measured memory_bytes: 74008
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = (int)(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = (int)(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define REVERSE(x) reverse((x).begin(), (x).end())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << '\n'
#define endl '\n'

constexpr int IINF = (1 << 30) - 1;
constexpr long long LLINF = 1LL << 61;
constexpr double EPS = 1e-10;

constexpr int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
constexpr int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

template<typename T>
bool chmax(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmin(T& a, T b){
    if(b < a){
        a = b;
        return true;
    }
    return false;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    string s;
    cin >> s;
    int n = (int)s.size();
    s.insert(s.begin(), '0');

    if(s[1] == '0'){
        cout << -1 << endl;
        return 0;
    }

    rep(i, n + 1){
        if(s[i] != s[n - i]){
            cout << -1 << endl;
            return 0;
        }
    }

    int now = n;
    rreps(i, n){
        if(i < n){
            cout << i << " " << now << endl;
        }
        if(s[i] == '1'){
            now = i;
        }
    }

    cout << flush;

    return 0;
}

Measured memory_bytes: 1616
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		boolean judje = true;

		Scanner scan = new Scanner(System.in);

		int A = scan.nextInt();
		int B = scan.nextInt();
		int C = scan.nextInt();
		int K = scan.nextInt();
		int sum = 0;

		if( K < A)
			sum += K;
		else
			sum += A;

		K -= (A + B);

		if( K > 0){
			sum -= K;
		}
		System.out.println(sum);
	}

}


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

using Int = int;
using namespace std;

#define ARC(i, a, b) for(Int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(Int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)
template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; };
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; };
template<class T> T th(T &a, const T &b, T (*f)(const T &, const T &)){ a = f(a, b); }
#define anth(a, b) th(a, b, ant)
#define onth(a, b) th(a, b, ont)

template<int MOD>
class modint{
    long long val;
public:
    modint(std::istream &is){ is >> val; }
    modint(long long val) : val(val) {}
    modint &operator=(const modint &a){
        val = a.val;
        return *this;
    }
    modint &operator+=(const modint &a){
        val += a.val;
        if(val >= MOD) val -= MOD;
        return *this;
    }
    modint &operator-=(const modint &a){
        if(val < a.val) val += MOD;
        val -= a.val;
        return *this;
    }
    modint &operator*=(const modint &a){
        val = (val * a.val) % MOD;
        return *this;
    }
    modint &operator^=(modint a){
        modint<MOD> tmp(val);
        val = 1;
        while(a.val){
            if(a.val & 1) *this *= tmp;
            tmp *= tmp;
            a.val >>= 1;
        }
        return *this;
    }
    modint &operator/=(modint rhs){
    long long exp = MOD - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
    friend std::ostream &operator<<(std::ostream &os, modint a){ return os << a.val; }
};
constexpr long long mod = 1000000007;
#define DEFOP(op) template<int MOD> modint<MOD> operator op(modint<MOD> a, modint<MOD> b){ return a op##= b; }
DEFOP(+) DEFOP(-) DEFOP(*) DEFOP(^) DEFOP(/)

Int n;
vector<map<Int, Int>> *p;
#define a (*p)

vector<bool> *q;
#define b (*q)

Int f(Int i){
	Int ret = 0;
	b[i] = 1;
	for(auto &j: a[i]){
		if(!b[j.first]){
			Int tmp = f(j.first);
			j.second = tmp;
			a[j.first][i] = n - tmp;
			ret += tmp;
		}
	}
	return ret + 1;
}

int main(){
	cin >> n;
	p = new vector<map<Int, Int>>(n);
	q = new vector<bool>(n, 0);
	RC(i, n - 1){
		Int x, y;
		cin >> x >> y;
		--x;
		--y;
		a[x].insert(make_pair(y, 0));
		a[y].insert(make_pair(x, 0));
	}
	f(0);

	modint<mod> ans = 0;
	RC(i, n){
		if(a[i].size() > 1){
			ans += modint<mod>(2) ^ modint<mod>(n - 1);
			for(auto j : a[i]){
				ans -= modint<mod>(2) ^ modint<mod>(j.second);
				ans += modint<mod>(1);
			}
			ans -= modint<mod>(1);
		}
	}

	ans /= modint<mod>(2) ^ modint<mod>(n);

	std::cout << ans << std::endl;

	delete p;
	delete q;
}


Measured memory_bytes: 41728
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long ll;

constexpr int MAX_N = 100005;
int used_topo[MAX_N];
vector<int> edg[MAX_N];

bool __rec_topo(vector<int> &topo, int pos) {
	if (used_topo[pos] == -1) return false;
	if (used_topo[pos] == 1) return true;
	used_topo[pos] = -1;
	for (int i : edg[pos]) {
		if (!__rec_topo(topo, i)) return false;
	}
	used_topo[pos] = 1;
	topo.push_back(pos);
	return true;
}

// topological sort vertices in the graph defined by edg
// n: the number of vertices
// the sorting result will be stored in the first argument topo
// returning false means the graph is not DAG
bool topo_sort(vector<int> &topo, int n) {
	bool flag = true;
	for (int i = 0; i < n; i++) {
		if (used_topo[i] == 0) flag &= __rec_topo(topo, i);
	}
	reverse(topo.begin(), topo.end());
	return flag;
}

ll dp[100005];

int main() {
	int n, m; cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		edg[x].push_back(y);
	}
	vector<int> topo;
	topo_sort(topo, n);
	for (int i : topo) {
		for (int e : edg[i]) {
			dp[e] = max(dp[e], dp[i] + 1);
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) ans = max(ans, dp[i]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9464
s = input()
t = input()

l = list(s)

for i in range(len(t)):
    if(''.join(l)  == t):
        print('Yes')
        exit()
    u = ''.join(l)
#    print(u)
    l = list(u)
    l.insert(0, l.pop())
    
print("No")

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

int main(){
  int n,k;
  cin >> n >> k;
  if(k>=n){cout << 0 << endl;
          return 0;}
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >>a.at(i); 
  }
  sort(a.begin(), a.end());
  long long ans=0;
  for(int i=0;i<n-k;i++){
    ans+=a.at(i);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  int N; cin >> N;
  vector<string> vecS(N);
  for(int i=0;i<N;i++){
    cin >> vecS.at(i);}
  
  int M; cin >> M;
  vector<string> vecT(M);
  for(int j=0;j<M;j++){
    cin >> vecT.at(j);}
  
  
  int max=0, sum=0;
  for(int k=0;k<N;k++){
    
    for(int l=0;l<N;l++){
      if(vecS.at(k) == vecS.at(l)){
        sum++;}
    }
    
    for(int m=0;m<M;m++){
      if(vecS.at(k) == vecT.at(m)){
        sum--;}
    }
    
    if(max < sum){max=sum;}
    sum=0;
  }
  
  cout << max << endl;
} 

Measured memory_bytes: 256
/*
ITP1_11_A
Dice 1

*/

#include<stdio.h>
#include<string.h>

struct DICE
{
  int *state;
  int *label;
};

int main(){
  int state[6] = {1,3,4,2,5,6}; ///{上,E,W.S,N,下}
  int label[6] = {1,2,3,4,5,6};
  struct DICE dice = {state,label};
  char s[101];
  int i,l, temp;
  for(i=0;i<6;i++){
    scanf("%d",&dice.label[i]);
  }
  scanf("%s",s);
  l = strlen(s);
  for (i=0;i<l;i++){
    if(s[i]=='E'){
      temp = dice.state[0];
      dice.state[0] = dice.state[2];
      dice.state[2] = dice.state[5];
      dice.state[5] = dice.state[1];
      dice.state[1] = temp;
    }
    else if(s[i]=='W'){
      temp = dice.state[0];
      dice.state[0] = dice.state[1];
      dice.state[1] = dice.state[5];
      dice.state[5] = dice.state[2];
      dice.state[2] = temp;
    }
    else if(s[i]=='S'){
      temp = dice.state[0];
      dice.state[0] = dice.state[4];
      dice.state[4] = dice.state[5];
      dice.state[5] = dice.state[3];
      dice.state[3] = temp;
    }
    else if(s[i]=='N'){
      temp = dice.state[0];
      dice.state[0] = dice.state[3];
      dice.state[3] = dice.state[5];
      dice.state[5] = dice.state[4];
      dice.state[4] = temp;
    }
  }
  printf("%d\n",dice.label[dice.state[0]-1]);

  return 0;
}



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

int main( int argc, char *argv[] )
{
int X;
int t;

	ios::sync_with_stdio( false );
	cin.tie( 0 );

	cin >> X;
	cin >> t;

	if( X > t )
		cout << X - t << endl;
	else
		cout << 0 << endl;

	return 0;
}




Measured memory_bytes: 256
import sys
N, M = [int(x) for x in input().split()]

if M * N == 1:
    print(1)
    sys.exit()

if N == 1:
    print(M - 2)
    sys.exit()

if M == 1:
    print(N - 2)
    sys.exit()
print(max((N - 2), 0) * max((M - 2), 0))


Measured memory_bytes: 2940
n=int(input())
l=[1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 4, 6, 8, 10, 12, 14, 16, 18, 3, 6, 9, 12, 15, 18, 21, 24, 27, 4, 8, 12, 16, 20, 24, 28, 32, 36, 5, 10, 15, 20, 25, 30, 35, 40, 45, 6, 12, 18, 24, 30, 36, 42, 48, 54, 7, 14, 21, 28, 35, 42, 49, 56, 63, 8, 16, 24, 32, 40, 48, 56, 64, 72, 9, 18, 27, 36, 45, 54, 63, 72, 81]
if n in l:
  print("Yes")
else:
  print("No")
  

Measured memory_bytes: 3064
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#include <random>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <random>
#include <time.h>
#include <chrono>
#include <sstream>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
#define SORT(s) sort(s.begin(), s.end());
#define reverse(s) reverse(s.begin(), s.end());
#define P pair<int,int>
#define mp make_pair
#define valid(x,y,h,w) (0<=x&&x<h&&0<=y&&y<w)
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }




int main() {
	string s;
	cin >> s;
	int a = 0, b = 0;
	rep(i, s.size()) {
		if (i%2 == 0 && s[i] == '1') {
			a++;
		}
		if (i % 2 == 1 && s[i] == '0') {
			a++;
		}
		if (i % 2 == 0 && s[i] == '0') {
			b++;
		}
		if (i % 2 == 1 && s[i] == '1') {
			b++;
		}
	}
	cout << min(a, b) << endl;
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
#define ll long long
#define fo(i,n) for(int i=0;i<n;i++)
#define rfo(i,n) for(int i=n-1;i>=0;i--)
#define Fo(i,q,n) for(int i=q;i<n;i++)
#define rFo(i,q,n) for(int i=n-1;i>=q;i--)
#define fO(i,n,k) for(int i=0;i<n;i+=k)
#define FO(i,q,n,k) for(int i=q;i<n;i+=k)
#define zero(a,n) memset(a,0,sizeof(a[0])*n)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define endl "\n"
#define Endl "\n"
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
using namespace std;
const int MOD=1000000007;
void print(){cout <<endl;}
template <typename T, typename... Types> 
void print(T var1, Types... var2){cout << var1 << " " ;print(var2...) ;}
//ceil of a/b
template <typename T>
T fceil(T a,T b){return (T)(a+b-1)/b;}
//const int N=2e5;
//int arr[N+1];

 
int main(){
	int n;
	cin>>n;
	vector<int> a(n,0);
	vector<int> b(n,0);
	vector<int> c(n,0);
	fo(i,n){
		cin>>a[i]>>b[i]>>c[i];	
	}
	
	vector< vector<int> > dp(n,vector<int>(3,0));
	dp[0][0]=a[0];
	dp[0][1]=b[0];
	dp[0][2]=c[0];
	fo(i,n){
		if(i==0){continue;}
		dp[i][0] = max(dp[i-1][1],dp[i-1][2])+a[i];
		dp[i][1] = max(dp[i-1][0],dp[i-1][2])+b[i];
		dp[i][2] = max(dp[i-1][1],dp[i-1][0])+c[i];
	}
	cout<< max({dp[n-1][0],dp[n-1][1],dp[n-1][2]})<<endl;
	return 0;
}






/*NOTE: Take MOD after sorting and not before sorting!*/


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n;
    cin >> n;
    vector<pll> vec(n);
    REP(i,n){
        int32 x, l;
        cin >> x >> l;
        vec[i] = pll(x + l, x - l);
    }
    sort(ALL(vec));
    int64 cur = -LLINF;
    int64 ans = 0;
    REP(i,n){
        if(cur > vec[i].second)continue;
        ans++;
        cur = vec[i].first;
    }
    ANS(ans);
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;
#define ll long long
#define FOR(i,n) for(int i=0;i<n;i++)
#define sz(x) (int)(x.size())
#define all(x) (x).begin(),(x).end()
template<typename tp> void read(tp &x) {cin >> x;}
template<typename tp, typename... Args> void read(tp& x, Args&... args) {read(x);read(args...);}
const int mxN = (int)1e5,INF = (int)1e9,MOD = (int)1e9+7;

void solve()
{
		int n;
		read(n);
		pair<int,int> a[n];
		FOR(i,n) read(a[i].first,a[i].second);
		for(int i=0;i<=n-3;i++)
		{
			if(a[i].first == a[i].second && a[i+1].first==a[i+1].second
			&&a[i+2].first == a[i+2].second
			)
			{
				cout << "Yes\n";
				return;
			}
		}
		cout << "No\n";
}

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



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

int main(){
  	long n, max_w;
  	cin >> n >> max_w;
  	long *w = new long[n];
  	long *v = new long[n];
  	long **dp = new long*[n];
  	for(int i = 0; i < n; i++)
      	dp[i] = new long[max_w+1];
  	for(int i = 0; i < n; i++)
      for(int j = 0; j < max_w+1; j++)
        dp[i][j] = 0;
  	for(int i = 0; i < n; i++){
    	cin >> w[i] >> v[i];
    }
    for(int i = w[0]; i < max_w + 1; i++)
        dp[0][i] = v[0];
 	for(int i = 1; i < n; i++){
      for(int j = 0; j < max_w + 1; j++){
      	long t1, t2;
        t1 = 0;
        if(j >= w[i])
          t1 = dp[i-1][j-w[i]] + v[i];         
       	t2 = dp[i-1][j];
        dp[i][j] = max(t1, t2); 
      }
    }
  	cout << dp[n-1][max_w];
	return 0;
}


Measured memory_bytes: 78592
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    string s;
    cin >> s;
    int n = s.length()+1;
    vint ans(n, -1);
    if (s[0] == '<') ans[0] = 0;
    if (s[n-2] == '>') ans[n-1] = 0;
    rep(i, n-2) {
        if (s[i] == '>' && s[i+1] == '<') ans[i+1] = 0;
    }
    rep(i, n-1) {
        if (s[i] == '<') ans[i+1] = ans[i] + 1;
    }
    rrep(i, n-1) {
        if (s[i] == '>') ans[i] = max(ans[i], ans[i+1] + 1);
    }
    ll total = 0;
    rep(i, n) total += ans[i];
    cout << total << endl;
    return 0;
}

Measured memory_bytes: 2820
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

int main(){
    iostream_init();
    string s;
    cin >> s;
    int n = s.size();
    vector<bool> a(n+1, false);
    a[0] = true;
    vector<string> v = {
        "dream",
        "dreamer",
        "erase",
        "eraser"
    };

    REP(i, s.size()) {
        if(a[i]) {
            for(auto t : v) {
                int ni = i + t.size();
                if(ni <= n && s.substr(i, t.size()) == t) {
                    a[ni] = true;
                }
            }
        }
    }
    cout << (a[n] ? "YES" : "NO") << endl;
    return 0;
}



Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 100000 + 100;
int N;
int A[Maxn];
int main()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
	int Ans = 1, fl; 
	if (A[2] > A[1])fl = 1;
	else if (A[2] < A[1])fl = 2;
	else fl = 0;
	for (int i = 3; i <= N; ++i)
	{
		if (fl == 1)
		{
			if (A[i] >= A[i - 1]) continue;
			else
			{
				++Ans;
				if (A[i + 1] < A[i])fl = 2;
				else if (A[i + 1] > A[i])fl = 1;
				else fl = 0;
				//++i;
			}
		}
		else if(fl == 2)
		{
			if (A[i] <= A[i - 1]) continue;
			else 
			{
				++ Ans;
				if (A[i + 1] > A[i]) fl = 1;
				else if (A[i + 1] < A[i]) fl = 2;
				else fl = 0;
				//++i;
			}
		}
		else 
		{
			if (A[i + 1] > A[i])fl = 1;
			else if (A[i + 1] < A[i])fl = 2;
			else fl = 0;
		}
	}
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#ifndef ONLINE_JUDGE
#define tr(...)
#define endl '\n'
#else
#include "../../tr.h"
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n, f[2], k;

int get(int x){
   return x*x*x;
}

int32_t main(){_

   cin>>n>>k;

   for (int i = 1; i <= n; ++i)
   {
      if(i%k == 0){
         f[0]++;
      }
      else if(i%k == k/2){
         f[1]++;
      }
   }

   tr(f[0], f[1]);
   int ans = get(f[0]);
   if(k%2 == 0){
      ans += get(f[1]);
   }
   cout<<ans;

   #warning make sure N size is correct!
   return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<cmath>
#include<cstring>
#include<set>
#include<climits>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define pb(b) push_back(b) 
#define all(a) a.begin(),a.end()
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define size(a,b) (a,vector<ll>(b))
const int mod=1e9+7;
/* 
UnionFind：素集合系管理の構造体(union by size)
isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))
unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))
treeSize(x): x を含む集合の要素数。
*/
struct UnionFind{
 vector<int>size,parents;
 UnionFind(){}
 UnionFind(int n){//make n trees.
  size.resize(n,0);
  parents.resize(n,0);
  for(int i=0;i<n;i++)makeTree(i);
 }
 void makeTree(int x){
   parents[x]=x;//the parent of x is x
   size[x]=1;
  }
 bool isSame(int x,int y){return findRoot(x)==findRoot(y);}
 bool unite(int x,int y){
  x = findRoot(x);
  y = findRoot(y);
  if(x==y)return false;
  if(size[x]>size[y]){
   parents[y]=x;
   size[x]+=size[y];
  } 
  else{
   parents[x]=y;
   size[y]+=size[x];
  }
  return true;
 }
 int findRoot(int x){//木の根を探す,計算量削減のため低く
  if(x!=parents[x])parents[x]=findRoot(parents[x]);
  return parents[x];
 }
 int treeSize(int x){return size[findRoot(x)];}
};
/*pi*/const double pi=acos(-1);
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
/*Fibonacci数列*/ll fib(ll x){ll i,fibo[x+10];fibo[0]=1;fibo[1]=1;fibo[2]=1;rep(i,3,x+1)fibo[i]=fibo[i-1]+fibo[i-2];return fibo[x];}
/*桁数*/ll dig(ll n){ll d=0,tmp=n;while(tmp/10>0){tmp/=10;d++;}return d;}
/*迷路移動*/const int dx[4]={1,0,-1,0};const int dy[4]={0,1,0,-1};
llfor;////////////////////////////////////////////////////////////
int main(){
 string s;
 cin>>s;
 bool used=false,now=false;
 ll cnt=0;
 string t="keyence";
 
 ll st,ed;
 ll n=s.length();
 rep(st,-1,n+1){
  rep(ed,st,n+1){
   string u="";
   rep(i,0,n){
    if(i<st||ed<i)u+=s[i];
   }
  // cout<<st<<" "<<ed<<" "<<u<<endl;
   if(u==t){
    pY;
    return 0;
   }
  }
 }
 pN;
return 0;}

Measured memory_bytes: 3632
import collections

n = int(input())
ln = list(map(int, input().split()))
m = int(input())
lm = list(map(int, input().split()))

c1 = collections.Counter(lm)
c2 = collections.Counter(ln)

for i in c1.keys():
    if c2[i] < c1[i]:
        print("NO")
        exit()

print("YES")

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

int main() {
  string s,t="";
  cin>>s>>t;
  int size=s.size();
  bool ans=true;
  
  rep (i,size){
    if(s.at(i)!=t.at(i)){
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
  return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int flag=0;
vector<int> hasfac(1000002,0);

void calcfac(int x)
{
    if(flag==1)
        return ;
    for(int i=1;i*i<=x;i++)
    {
        int a,b;
        if(x%i==0)
        {

                a=i;
                b=x/i;

            if(a==b){
                a=i;
                b=1;
            }


        if(a!=1)
        {

        if(hasfac[a]!=0)
        {
            flag=1;
            return;
        }

            hasfac[a]++;
        }

        if(b!=1)
        {
           if(hasfac[b]!=0)
            {
                flag=1;
                return;
            }

                hasfac[b]++;

        }
    }

}
}
int main()
{
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    calcfac(arr[0]);
    int gcd=arr[0];
    for(int i=1;i<n;i++)
    {

        calcfac(arr[i]);
        gcd=__gcd(gcd,arr[i]);

    }
    if(flag==0)
        cout<<"pairwise coprime";
    else if(gcd==1)
        cout<<"setwise coprime";
    else
        cout<<"not coprime\n";

}


Measured memory_bytes: 11124
#include<iostream>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>

using namespace std;

int n;
long long a[100005];
long long b[100005];
long long c[100005];


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

  sort(a,a+n);
  sort(b,b+n);
  sort(c,c+n);

  long long ans[100005];

  int p=0;
  for(int i=0;i<n;i++){
    while(c[p] <= b[i]){
      if(p==n) break;
      p++;
    }
    ans[i] = n-p;
  }

  for(int i=n-2;i>=0;i--)ans[i] += ans[i+1];

  long long ans2 = 0;
  p=0;
  for(int i=0;i<n;i++){
    while(b[p] <= a[i]){
      if(p==n) break;
      p++;
    }
    if(p == n) continue;
    ans2 += ans[p];
  }

  cout<<ans2<<endl;
  return 0;
}

Measured memory_bytes: 3328
#include <iostream>
using namespace std;
int n, m, a[55], b[55], c[55], d[55];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
	for (int i = 1; i <= m; i++) scanf("%d%d", &c[i], &d[i]);
	for (int i = 1; i <= n; i++) {
		int e = -1;
		for (int j = 1; j <= m; j++) if (e == -1 || abs(a[i]-c[j])+abs(b[i]-d[j])<abs(a[i]-c[e])+abs(b[i]-d[e])) e=j;
		printf("%d\n", e);
	}
	return 0;	
}

Measured memory_bytes: 256
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
memo = {}
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  k = (nokori, current)
  if k in memo:
    return memo[k]
  if nokori <= 0:
    return current if nokori == 0 else -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          # 98 ok, 89 重複するので最後の桁以外は skip
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  memo[k] = max(temps)
  return memo[k]

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Measured memory_bytes: 12776
#include <iostream>
using namespace std;
int main()
{
  int m,f,r;
  char g;
  while(1)
  {
    cin>>m>>f>>r;
    if(m==-1&&f==-1&&r==-1) break;
    if(m==-1||f==-1)
      g='F';
    else
    {
      if ((m+f)>=80)
        g='A';
      else if ((m+f)>=65)
        g='B';
      else if ((m+f)>=50)
        g='C';
      else if ((m+f)>=30)
      {
        g='D';
        if(r>=50)
          g='C';
      }
      else
        g='F';
    }
    cout<<g<<endl;
  }
}

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

int main() {
  int N, K;
  scanf("%d %d\n", &N, &K);
  vector<int> h(N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &h[i]);
  }

  vector<int> dp(N);
  dp[0] = 0;
  for (int i = 1; i < N; i++) {
    int ans = INT_MAX;
    for (int j = 1; j <= K; j++) {
      int prev = i - j;
      if (prev < 0) break;
      ans = min(ans, dp[prev] + abs(h[i] - h[prev]));
    }
    dp[i] = ans;
  }

  printf("%d\n", dp[N-1]);
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}

int kai(int x) {
	if (x == 1)return 1;
	return kai(x - 1)*x%mod;
}

int mod_pow(int x, int y, int moder) {
	int res = 1;
	while (y > 0) {
		if (y & 1)res = res * x%moder;
		x = x * x%moder;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	if (x == y)return 1;
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

int n, a[200000];
int ta[200010];
set<int> st, sr;//st=正 sr=負
int ans;

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		ta[a[i]] = i;
	}
	ans += (ta[1] + 1)*(n - ta[1]);
	st.insert(ta[1]);
	sr.insert(-ta[1]);
	for (int i = 2; i <= n; i++) {
		if (*st.rbegin() < ta[i])ans += i * (ta[i] - *st.rbegin())*(n - ta[i]);
		else if (ta[i] < *st.begin())ans += i * (ta[i] + 1)*(*st.begin() - ta[i]);
		else {
			int x = *st.lower_bound(ta[i]);
			int y = -*sr.lower_bound(-ta[i]);
			ans += i * (ta[i] - y)*(x - ta[i]);
			
		}
		st.insert(ta[i]);
		sr.insert(-ta[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 22144
#include<bits/stdc++.h>
using namespace std ;
#define ll  long long 
#define dl long double
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second


int main ()
{
	
	ll n,m,k;
	cin >>n>>m>>k;
	ll arr[n],brr[m];
    vector<ll>va;
	vector<ll>vb;
	ll a=0;

	for (int i = 0 ;i<n;i++)
		cin>>arr[i];
	for (int i = 0 ;i<m;i++)
		cin>>brr[i];
	
	for (int i =0 ;i<=n;i++){
		va.pb(a);
		a+=arr[i];	
	}
    a=0;
	for (int i =0 ;i<=m;i++){
		vb.pb(a);
		a+=brr[i];	
	}
    ll ans=0 ,j,yes=0;
    for (int i = 0 ;i<va.size();i++)
    {
        yes=k-va[i];
        if (yes<0)
        	continue;
        j = lower_bound(vb.begin(),vb.end(),yes)-vb.begin();
         
        if (vb[j]>yes || j>m)
         	j--;
        if (j+i>ans)
        ans=j+i;
    }
    cout<<ans<<endl;

	return 0;

}

Measured memory_bytes: 11108
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let s: String = read();
    println!("{}", 700 + s.chars().filter(|&c| c == 'o').count() * 100);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

int N;
int H[21];  

int main() {
  cin >> N;
  for (int i = 0; i < N; ++i) cin >> H[i];
  int cnt = 1;
  
  if(N > 1){
     
  for (int i = 1; i < N; ++i){
    bool isGreatView = true;
    for (int j = 0; j < i; j++){
      if(H[i] < H[j]) isGreatView = false;
    }
    if(isGreatView) ++cnt; 
  }
    
  }

  cout << cnt << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define all(a) a.begin(),a.end()
#define lb(s,x) lower_bound(all(s),x)-s.begin()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define INF 1e9
typedef long long ll;

int main(void){
    int n;
    ll a,b;
    cin>>n>>a>>b;
    vector<ll> x(n);
    rep(i,n){
        cin>>x[i];
    }
    ll res = 0;
    rep(i,n-1){
        res += min((x[i+1]-x[i])*a, b);
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 1024
import math
n = int(input())
ls_st = [list(input().split()) for i in range(n)]
x = str(input())
ans = 0
for i in range(n):
    ls_st[i][1] = int(ls_st[i][1])
# print(ls_st.index(x))
# print(ls_st)
# arr = [["A", "B", "C"], ["D", "E", "F"], ["G", "H", "I"]]

for y, row in enumerate(ls_st):
    try:
        pos = (y, row.index(x))
        break
    except ValueError:
        pass
for i in range(pos[0]+1,n):
    ans += ls_st[i][1]

print(ans)

Measured memory_bytes: 3064
#include<iostream>

using namespace std;

int main()
{
  int h,m,h2,m2,k,tmp;
  cin >> h >> m >> h2 >> m2 >> k;
  int time;
  time = (h2-h) * 60;
  time += m2 - m;

  if(time <= k)
    cout << "0\n";
  else
    cout << time - k << '\n';


}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[200050]={0};
    int k, n, i, b, c=0, d=0;
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
        cin>>b;
        a[b]++;
    }
    sort(a+1, a+n+1);
    for(i=n;i>=1;i--)
    {
        d++;
        c+=a[i];
        if(d==k)
            break;
    }
    cout<<n-c<<endl;
    return 0;
}

Measured memory_bytes: 1024
inf = int(1e9+7)
mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    n, k = [int(x) for x in raw_input().split()]
    
    arr = [(1 + float(x)) / 2 for x in raw_input().split()]
    
    if k == 1:
        print(max(arr))
        return
    
    #print(arr)
    """
    total = sum(probs)
    
    arr = [0] * n
    
    for i in range(n):
        arr[i] = float(i) * (probs[i] / total)
    
    print(arr)
    """
    
    pref_sum = [0] * n
    
    pref_sum[0] = arr[0]
    
    for i in range(1, n):
        pref_sum[i] = pref_sum[i-1] + arr[i]
    
    #print(pref_sum)
    
    max_sub = -inf
    
    for end in range(k-1, n):
        start = end - k + 1
        # length = end - (end - k) + 1 = k + 1
        cur = pref_sum[end] # - pref_sum[start-1]
        if start > 0:
            cur -= pref_sum[start-1]
        if cur > max_sub:
            max_sub = cur
        
    
    
    print(max_sub)

main()

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

int main()
{
  int n;
cin >> n;
  
  vector<int64_t> data(n);
  for(int i=0; i<n; ++i) {
    cin >> data[i];
  }

  int fin = 0;
  for(int i=0; i<n-1; ++i){
    if( data[i] < data[i+1] ){
     	fin = i; 
    }
  }
  
  int64_t g = 1000LL;
  int64_t k = 0LL;
  for(int i=0; i<n; ++i){
    if ( i > fin ) {
      g += (int64_t)data[i] * k;
      k= 0ll;
      break;
    }
    else if( data[i] < data[i+1] ){
      //while(g >= data[i]) {
      //  g -= data[i];
      //  k ++;
      //}
      int64_t num = g / data[i];
      int64_t u = num * (int64_t)data[i];
      g -= u;
      k += num;
    } else if( data[i] > data[i+1] ){
      g += int64_t(data[i]) * k;
      k = 0LL;
    }
  }
  
  cout << g;
    return 0;
}


Measured memory_bytes: 3580
#include<iostream>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<map>
#include<queue>
#include<stack>

using namespace std;

int main()
{
    int m,n;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int mx=(n-1)*(m-1);
        printf("%d\n",mx);
    }
    return 0;
}


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

const long long c = 998244353;

long long power(long long x, long long y) 
{ 
    long long res = 1;
  
    x = x % c; 
    while (y > 0) 
    { 
        
        if (y & 1) 
            res = (res*x) % c; 
  
        
        y = y>>1; 
        x = (x*x) % c;   
    } 
    return res; 
} 
int main(){
  long long N ;
  cin>>N;
  vector<long long> D(N);
  for(long long i = 0 ; i < N ; i++) cin>>D[i];
  if(D[0] != 0) 
  {
  	cout<<0<<endl;
  	return 0;
  }
  if(N == 1)
  {
  	cout<<1<<endl;
  	return 0;
  }
  sort(D.begin(),D.end());
  if(D[1] == D[0])
  {
  	cout<<0<<endl;
  	return 0;
  }
  vector<long long> A(N,0);
  for(long long i = 1 ; i < N ; i++)
  {
  	A[D[i]-1]++;
  }
  long long ans = 1;
  long long temp = 1;
  bool flag = false;
  for(long long i = 0 ; i < N ; i++)
  {
  	if(A[i] == 0) flag = true;
  	else if(flag == true && A[i]!=0) 
  	{
  		cout<<0<<endl;
  		return 0;
  	}
  	else 
  	{
  		long long temp_1 = power(temp,A[i]);
  		ans = ((ans*(temp_1))%c);
  		temp = A[i];
  	}
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define drep(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int sz=310;
const int mod=1e9+7;
int n,m;
int dp[sz][sz][sz];
int main(){
	scanf("%d%d",&n,&m);
	dp[0][1][0]=1;
	rep(i,0,m-1){
		rep(j,0,n){
			rep(k,0,n){
				int cur=dp[i][j][k];
				dp[i+1][j][k]=(dp[i+1][j][k]+1ll*cur*k%mod)%mod;
				dp[i+1][j][k+1]=(dp[i+1][j][k+1]+1ll*cur*(n-j-k)%mod)%mod;
				dp[i+1][j+k][0]=(dp[i+1][j+k][0]+1ll*cur*j%mod)%mod;
			}
		}
	}
	printf("%d\n",dp[m][n][0]);
}

Measured memory_bytes: 114560