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

#define gcd(a,b)     __gcd(a,b)
#define lcm(a,b)     (a*(b/gcd(a,b)))

#define pb   push_back
#define endl "\n"

#define ll  long long
#define ull unsigned long long

#define W(t)            while(t--)
#define rep1(i,n)       for(int i = 0; i < n; i++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

int main()
{
    IOS
    ll t,n,i;
    string s;
    cin>>n;

    if(n>= 400 && n<= 599)
        cout<<8;
    else if(n>= 600 && n<= 799)
        cout<<7;
    else if(n>= 800 && n<= 999)
        cout<<6;
    else if(n>= 1000 && n<= 1199)
        cout<<5;
    else if(n>= 1200 && n<= 1399)
        cout<<4;
    else if(n>= 1400 && n<= 1599)
        cout<<3;
    else if(n>= 1600 && n<= 1799)
        cout<<2;
     else
          cout<<1;


    return 0;
}


Measured memory_bytes: 3632
H, W = map(int, input().split())
field = []
for _ in range(H):
    tmp = input()
    if tmp.count('#') == 0:
        continue
    else:
        field.append(tmp)
ans_field = [""] * len(field)
for column in range(W):
    del_flag = True
    for row in range(len(field)):
        if field[row][column] == '#':
            del_flag = False
            break
    if not del_flag:
        for row in range(len(field)):
            ans_field[row] += field[row][column]
for val in ans_field:
    print(val)


Measured memory_bytes: 9148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<bool>> vvb;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define vrep(v,n) for(int i=0;i<n;i++){cin >> v.at(i);} 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int mod = 1000000007;
const int inf = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};




int main(){
    int n, k;
    cin >> n >> k;
    vector<int> h(n); 
    rep(i,n) cin >> h[i];
    vector<bool> w(n, true);
    rep(i,k){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if(h[a] > h[b]) w[b] = false;
        else if(h[a] < h[b]) w[a] = false;
        else w[a] = w[b] = false;
    }
    int ans = 0;
    for(auto e : w){
        if(e) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3792
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1047483600
#define long long long // for codeforces

int main(){
  int n;
  cin>>n;
  vector<int> vec(n);
  rep(i,n-1) cin>>vec[i];

  vector<vector<int>> dp(n+1, vector<int>(2, INF));
  // [len A][0A 1B]
  dp[1][0] = 0;
  dp[0][1] = 0;

  repl(i,1,n){
    vector<vector<int>> nxt(n+1, vector<int>(2, INF));
    rep(j,n/2+1){
      nxt[j][1] = min(nxt[j][1], dp[j][0] + vec[i-1]);
      nxt[j+1][0] = min(nxt[j+1][0], dp[j][0]);
      nxt[j+1][0] = min(nxt[j+1][0], dp[j][1] + vec[i-1]);
      nxt[j][1] = min(nxt[j][1], dp[j][1]);
    }
    swap(nxt, dp);
  }
  cout << dp[n/2][0] << endl;

  return 0;
}

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

int main(void){
    int n,m;
    cin >> n >> m;
    if (n<=m) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#ifdef __GNUC__

#define iss std::cin
#endif
#include "bits/stdc++.h"
#define rep(i, times) for(ll i = 0; i < (times); ++i)
#define p(x) (cout << (x) << "\n")
using ll = long long; using ld = long double; using namespace std;

#ifndef __GNUC__
string text =
R"X(
6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288
)X";
stringstream iss{text};
#endif 

class Festival
{
	ll N{0};
	vector<vector<ll>> A;
	void inp( ) {
		iss >> N; A.resize(3, vector<ll>(N));
		rep(a, 3) {	rep(i, N) { iss >> A[a][i]; };}
		sort(begin(A[0]), end(A[0]));
		sort(begin(A[2]), end(A[2]));
	}
	void biSearch( ) {
		ll cnt{0};
		for (auto &b : A[1]) {
			auto itA = lower_bound(begin(A[0]), end(A[0]), b);//A<bなる最大要素の位置
			auto itC = upper_bound(begin(A[2]), end(A[2]), b);//b<Cなる最小要素の位置
			cnt += (end(A[2]) - itC) * (itA - begin(A[0]));
		}
		p(cnt);
	}
public:
	void procedures( ) {
		inp( );	biSearch( );
	}
};
int main( ) {
	cin.tie(0);	ios::sync_with_stdio(0);
	class Festival a; a.procedures( );
}

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

bool check(string s){
    int n = s.size();
    rep(i,n){
        if (s[i] != s[n-1-i]) return false;
    }
    return true;
}

int main(void){
    string s;
    cin >> s;
    int n = s.size();
    bool b1 = check(s);
    bool b2 = check(s.substr(0, (n-1)/2));
    bool b3 = check(s.substr((n+3)/2-1, n-(n+3)/2+1));
    cout << ((b1 && b2 && b3) ? "Yes" : "No") << endl;
    return 0;
}


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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
  int n;
  cin >> n;
  for(int i=0;i<100;i++){
    for(int j=0;j<100;j++){
      if(4*i+7*j==n){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
D1 = [0] * N
D2 = [0] * N
for i in range(N):
    D1[i], D2[i] = map(int, input().split())
c = 0
a = 0
    
for d1, d2 in zip(D1, D2):
  if d1 == d2:
    c += 1
  else:
    c = 0
  if c >= 3:
    print("Yes")
    break

if c < 3:
  print("No")

Measured memory_bytes: 9188
#include "bits/stdc++.h"
#define YESNO OUT(three(solve(),"YES","NO"))
#define YesNo OUT(three(solve(),"Yes","No"))
#define WL(A,B) OUT(three(solve(),A,B))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(b);i>=(LL)(a);i--)
#define REP(i,b) FOR(i,zero,b)
#define rep REP
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define zero 0LL
#define all ALL
#define pb emplace_back
#define eb pb
#define int long long
using namespace std;
template<typename T> inline void maximize(T &a, T b) { a = max(a, b); }
template<typename T> inline void minimize(T &a, T b) { a = min(a, b); }
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
template<class T> inline bool chmax(int a, int b, T c, T d) { return c > d ? a : b; }
template<class T> inline bool chmin(int a, int b, T c, T d) { return c > d ? a : b; }
typedef int LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef tuple<int, int, int, int> tapu;
typedef vector<tapu> Vtapu;
typedef priority_queue<ut, VI, greater<LL> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
const int SIZE1 = 1e6 + 1000;
const int SIZE2 = 2010;
const int SIZE3 = 430;
const int SIZE = SIZE1;
const int MAPSIZE = 40;
const LL p = 7 + 1e9;
const LL INF = 1LL << 30;
const long double EPS = 1e-7;
const LL inf = 1000000000;
typedef pair<ld, ut> pld;
ut N, M, K, L, Q,  H, W, R;
VI edges[SIZE];
LL vals[SIZE], answer = zero;
LL maps[SIZE2][SIZE2];
//LL A[SIZE],B[SIZE],C[SIZE],D[SIZE],E[SIZE];
LL  A, B;

LL solve() {
	cin >> K >> A >> B;
	LL ans = 0;
	if (A >= B+2) {

		return K+1;
	}
	else {
		K++;
		LL ans = K;
		MX(ans, (K - A) / 2 * (B - A) + (K - A) % 2 + A);

		return ans;
	}
	
}




//!!!!!!!!!!!!!!!!!!!実装を詰める!!!!!!!!!!!!!!!!!!!!!!!!!
signed main() {

	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(0);
	cout << solve() << endl;
	
	//cin >> N;
	return 0;

}

Measured memory_bytes: 24192
// ---------- begin SegmentTree Point update Range query ----------
mod segment_tree {
    pub struct PURQ<T: Clone, F: Fn(T, T) -> T> {
        n: usize,
        a: Vec<T>,
        id: T,
        op: F,
    }
    #[allow(dead_code)]
    impl<T: Clone, F: Fn(T, T) -> T> PURQ<T, F> {
        pub fn new(n: usize, id: T, op: F) -> PURQ<T, F> {
            let mut k = 1;
            while k < n {
                k *= 2;
            }
            PURQ {
                n: k,
                a: vec![id.clone(); 2 * k],
                id: id,
                op: op,
            }
        }
        pub fn update(&mut self, x: usize, v: T) {
            let mut k = self.n + x;
            let a = &mut self.a;
            a[k] = v;
            k >>= 1;
            while k > 0 {
                a[k] = (self.op)(a[2 * k].clone(), a[2 * k + 1].clone());
                k >>= 1;
            }
        }
        pub fn update_tmp(&mut self, x: usize, v: T) {
            self.a[x + self.n] = v;
        }
        pub fn update_all(&mut self) {
            for k in (1..(self.n)).rev() {
                self.a[k] = (self.op)(self.a[2 * k].clone(), self.a[2 * k + 1].clone());
            }
        }
        pub fn find(&self, mut l: usize, mut r: usize) -> T {
            let mut p = self.id.clone();
            let mut q = self.id.clone();
            l += self.n;
            r += self.n;
            while l < r {
                if (l & 1) == 1 {
                    p = (self.op)(p, self.a[l].clone());
                    l += 1;
                }
                if (r & 1) == 1 {
                    r -= 1;
                    q = (self.op)(self.a[r].clone(), q);
                }
                l >>= 1;
                r >>= 1;
            }
            (self.op)(p, q)
        }
    }
}
// ---------- end SegmentTree Point update Range query ----------

use proconio::*;
use proconio::marker::*;

fn run() {
    input! {
        h: usize,
        w: usize,
        m: usize,
        p: [(Usize1, Usize1); m],
    }
    let mut g = vec![vec![]; h];
    let mut cnt = vec![0; w];
    for (a, b) in p {
        g[a].push(b);
        cnt[b] += 1;
    }
    let mut seg = segment_tree::PURQ::new(w, 0, |a, b| std::cmp::max(a, b));
    for i in 0..w {
        seg.update_tmp(i, cnt[i]);
    }
    seg.update_all();
    let mut ans = 0;
    for g in g {
        for &x in g.iter() {
            seg.update(x, cnt[x] - 1);
        }
        ans = std::cmp::max(ans, seg.find(0, w) + g.len());
        for &x in g.iter() {
            seg.update(x, cnt[x]);
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    int n,m,x;cin>>n>>m>>x;
    int pre=0,post=0;
    for(int i=0;i<m;i++){
        int a;cin>>a;
        if(a<x) pre++;
        else post++;
    }
    cout<<min(pre,post)<<endl;
}


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

typedef long long ll;

int main(){
	cout.precision(13);
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	const int N = 86400;
	const int M = 10800 + 1;
	int cnt[N] = {};
	int n;
	cin >> n;
	int t = 0;
	for(int i = 0;i < n; ++i){
		int x,y;
		cin >> x >> y;	
		t+=x;
		++cnt[t % N];
		t+=y;
		t%=N;
	}
	int csum = accumulate(cnt, cnt + M, 0);
	int ans = csum;
	for(int i = 0;i < N; ++i){
		csum += cnt[(i + M) % N];
		csum -= cnt[i];
		ans = max(ans, csum);
	}
	cout << ans << '\n';
}


Measured memory_bytes: 640
// clang-format off
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i,n) for(ll i=n-1; i>=0; --i)
#define rrep1(i,n) for(ll i=n; i>0; --i)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define SORT_DESC(x) sort((x).rbegin(),(x).rend())
#define pb push_back
#define mp make_pair
#define coutl cout<<fixed<<setprecision(10)
#define ANS(ans) cout<<ans<<endl
#define END(ans) ANS(ans); return
const ll LINF = (1LL << 62) - 1;
const int INF = (1 << 30) - 1;
template<class T>inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if (b<a){a=b;return 1;}return 0;}
// clang-format on

void solve(long long N, std::vector<long long> h) {
  vector<ll> dp(N, INF);
  dp[0] = 0;
  rep(i, N) {
    chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
    chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
  }
  ANS(dp[N - 1]);
}

// clang-format off
int main() {
  long long N;
  scanf("%lld",&N);
  std::vector<long long> h(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&h[i]);
  }
  solve(N, std::move(h));
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin>>tests;
    rep(test,0,tests) {
        int n;
        cin>>n;
        vector<ll> a(n);
        string s;
        rep(i,0,n) cin>>a[i];
        cin>>s;
        vector<ll> basis;
        int ans = 0;
        for(int i=n-1;i>=0;--i) {
            ll x = a[i];
            for(ll y:basis) {
                x = min(x,x^y);
            }
            if(x!=0) {
                if(s[i]=='1') {
                    ans = 1;
                    break;
                }
                else {
                    basis.push_back(x);
                }
            }
        }
        cout<<ans<<"\n";

    }
}


Measured memory_bytes: 3612
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def light_length(a:int, b:int) -> int:
    if a > b:
        a,b = b,a
    
    if b%a == 0:
        return 2 * a * (b//a) - a

    return 2 * (b//a) * a + light_length(a, b%a)

n,x = li()

print(n + light_length(x,n-x))  

Measured memory_bytes: 3064
#include<stdio.h>

int main(void){
    int n=0 ,i ,x ;
    scanf("%d",&n);

    for (i=1 ;i<n+1 ;i++){
        x=i;
        if ((x%3)==0){
            printf(" %d",i);
        } else while(1){
            if ((x%10)==3){
                printf(" %d",i);
                break;
            }
            x/=10;
            if (!x) break;
        }
    }

    printf("\n");
    return 0;
}

Measured memory_bytes: 2752
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
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;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)

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

  vector<set<ll>> st(26);
  for (ll j = 0; j < 26; j++)
  {
    st.at(j).emplace(-1);
    st.at(j).emplace(N);
  }

  for (ll i = 0; i < N; i++)
  {
    st.at(S.at(i) - 'a').emplace(i);
  }

  ll Q;
  cin >> Q;
  for (ll q = 0; q < Q; q++)
  {
    ll qt;
    cin >> qt;
    if (qt == 1)
    {
      ll i;
      char c;
      cin >> i >> c;
      i--;

      st.at(S.at(i) - 'a').erase(i);
      S.at(i) = c;
      st.at(c - 'a').emplace(i);
    }
    else
    {
      ll l, r;
      cin >> l >> r;
      l--, r--;

      ll ans = 0;
      for (ll j = 0; j < 26; j++)
      {
        auto it = st.at(j).lower_bound(l);
        ans += (*it <= r);
      }
      cout << ans << endl;
    }
  }
}

Measured memory_bytes: 24196
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
lis=[[0]*(w+2) for i in range(h+2)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]==".":
            lis[i+1][j+1]=1
#print(lis)
step=[[1,0],[0,-1],[-1,0],[0,1]]
counter=[[-1]*(w+2) for i in range(h+2)]
counter[1][1]=0
q=deque([[1,1]])
while q:
    x,y=q.popleft()
    #print(x,y)
    for i,j in step:
        if counter[x+i][y+j]<0 and lis[x+i][y+j]==1:
            q.append([x+i,y+j])
            counter[x+i][y+j]=counter[x][y]+1
if counter[h][w]<0:
    print(-1)
    sys.exit()
white=0
for i in range(h+2):
    white+=sum(lis[i])
#print(white)
if lis[1][1]==1:
    white-=1
ans=white-counter[h][w]
print(ans)
#print(counter[h][w])


Measured memory_bytes: 40944
#include <iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int count=0;
    int k;
    cin>>k;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a>=k){
            count++;
        }
    }
    cout<<count<<endl;
}


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

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

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

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N; std::cin >> N;
  vector<ll> P(N); REP(i, N) std::cin >> P[i];
  vector<pair<ll, ll>> value_idx(N);
  REP(i, N) value_idx[i] = std::make_pair(P[i], (ll)i);
  std::sort(ALL(value_idx));

  multiset<int> mset = {-1, -1, N, N};
  ll ans = 0;
  for (int i = N-1; i >= 0; i--) {
    ll value, idx; tie(value, idx) = value_idx[i];
    auto it = mset.insert(idx);
    it--; ll l1 = *it;
    it--; ll l2 = *it;
    it = mset.find(idx);
    it++; ll r1 = *it;
    it++; ll r2 = *it;
    ans += ((l1 - l2) * (r1 - idx) + (r2 - r1) * (idx - l1)) * value;
  }
  std::cout << ans << endl;
  return 0;
}


Measured memory_bytes: 10300
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

void solve(int curr, int prev, const vector<vector<int> >& edges, vector<int>& val)
{
    for(int next : edges[curr]){
        if(next == prev)
            continue;
        val[next] += val[curr];
        solve(next, curr, edges, val);
    }
}

int main()
{
    int n, q;
    cin >> n >> q;

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

    vector<int> val(n, 0);
    for(int i=0; i<q; ++i){
        int p, x;
        cin >> p >> x;
        -- p;
        val[p] += x;
    }

    solve(0, -1, edges, val);
    cout << val[0];
    for(int i=1; i<n; ++i)
        cout << ' ' << val[i];
    cout << endl;

    return 0;
}


Measured memory_bytes: 29696
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    a, b = list(map(int, input().rstrip('\n').split()))
    ls = []
    ls.append(str(b) * a)
    ls.append(str(a) * b)
    ls.sort()
    print(ls[0])


if __name__ == '__main__':
    solve()


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<ll, ll>;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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 vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}
struct edge {
  ll to, cost;
};

int main() {
  int A, B, C; cin >> A >> B >> C;
  if(A <= C && C <= B) cout << "Yes" << endl;
  else if(B <= C && C <= A) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3584
#include<stdio.h>

int main(){
  int n;
  int k;
  int a[100];
  int cnt=0;
  scanf("%d",&n);
  for(k=0;k<n;k++){
    scanf("%d",&a[k]);
    if(a[k]%2==0)
      if((a[k]%3!=0 ) && (a[k]%5!=0)){
	printf("DENIED");
	return 0;
      }
  }
  printf("APPROVED");
  return 0;
 
}

Measured memory_bytes: 128
count = {1:0,2:0,3:0,4:0}
for n in range(3):
    a,b = [int(i) for i in input().split()]
    count[a] += 1
    count[b] += 1

    if (count[a] > 2 or count[b] > 2):
        print("NO")
        exit(0)

print("YES")


Measured memory_bytes: 2940
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

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

	int n;
	cin >> n;

	long long k;
	cin >> k;

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

	vector<int> visited(n + 1);
	int t = 1;
	while (visited[t] == 0) {
		visited[t] = 1;
		t = towns[t];
	}

	int curr = 1;
	while (curr != t && k) {
		curr = towns[curr];
		--k;
	}	

	if (!k) {
		cout << curr << "\n";
	} else {
		int loop_size = 1;
		int curr = towns[t];
		while (curr != t) {
			curr = towns[curr];
			++loop_size;
		}

		k %= loop_size;	
		while (k) {
			t = towns[t];
			--k;
		}

		cout << t << "\n";
	}

	return 0;

}

Measured memory_bytes: 4772
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

using namespace std;

#define REP(x,l,u) for(ll x = l; x < u; x++)
#define RREP(x,l,u) for(ll x = l; x >= u; x--)

string to_string(string s) {return s;}
string to_string(char c) {string s = string(1, c);return s;}
template <typename A, typename B> string to_string(pair<A,B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A> string to_string(vector<A> v) { string s = "("; int first = 1; for (A a : v) { if (!first) { s += ", "; } first = 0; s += to_string(a); } s += ")"; return s; }
template <typename A> string to_string(set<A> v) { string s = "("; int first = 1; for (A a : v) { if (!first) { s += ", "; } first = 0; s += to_string(a); } s += ")"; return s; }

void debug_out() {cerr << endl;}
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); }

#ifndef ONLINE_JUDGE
#define debug(...) do { cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__); } while (false)
#else
#define debug(...) do { } while (false)
#endif

typedef long long ll;
typedef double db;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef pair<ll,ll> PLL;
typedef vector<string> VS;

void in(string & s) {
	char buf[1005]; // note the 100 limit
	ll a = scanf("%1004s", buf);
	s = buf;
}

void in(ll & x) {
	ll a = scanf("%lld", &x);
}

const ll inf = (ll)1e18 + 5;

VLL parent;

ll get_parent(ll x) {
	if (parent[x] == x) return x;

	ll top = get_parent(parent[x]);

	parent[x] = top;

	return top;
}

bool same(ll a, ll b) {
	if (get_parent(a) == get_parent(b)) return true;
	
	return false;
}

void merge(ll a, ll b) {
	if (same(a,b)) {
		return;
	}

	parent[get_parent(a)] = parent[get_parent(b)];
}

void solve() {

	ll n, q;

	cin >> n >> q;

	REP(i,0,n) {
		parent.push_back(i);
	}

	REP(i,0,q) {
		ll act, a, b;

		cin >> act >> a >> b;

		if (act) {
			// check if they are in the same
			cout << same(a,b) << endl;
		} else {
			// merge parents
			merge(a,b);
		}
	}
}

signed main() {
	ll t = 1;
	REP(i,0,t) solve();
	return 0;
}


Measured memory_bytes: 3376
#include<bits/stdc++.h>
using namespace std;
int v[1001];
int w[1001];
int dp[101][10001];
int N,W;
int solve(int a,int b);
int main(){
  cin >> N >> W;
  for(int i=0;i<N;i++){
    cin >> v[i] >> w[i];
  }
  cout << solve(0,W) << endl;
  
}
int solve(int a,int b){
  if(dp[a][b] != 0)return dp[a][b];
  if(a == N){
    return dp[a][b] = 0;
  }else if(b - w[a] < 0){
    return dp[a][b] = solve(a+1,b);
  }
  else{
    return dp[a][b] = max(solve(a,b-w[a])+v[a],max(solve(a+1,b),solve(a+1,b-w[a])+v[a])) ;
  }
}

Measured memory_bytes: 5700
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, delimiter=' '): print(delimiter.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N_AROUND = 8
ddx = (-1, 0, 1, -1, 1, -1, 0, 1)
ddy = (-1, -1, -1, 0, 0, 1, 1, 1)

H, W = iInM()
S = sInLV(H)

## 周りに空きマスを入れる
T = [['.'] * (W + 2)]
for i in range(H):
    var = ['.'] + list(S[i]) + ['.']
    T.append(var)
T.append(['.'] * (W + 2))
#OutV(T)

ans = []
for i in range(1, H+1):
    ans.append([])
    for j in range(1, W+1):
        if T[i][j] == '#':
            ans[-1].append('#')
            continue
        cnt = 0
        for k in range(N_AROUND):
            if T[i + ddy[k]][j + ddx[k]] == '#':
                cnt += 1
        ans[-1].append(str(cnt))
        #print(ans)
#OutV(ans)

for i in range(H):
    OutH(ans[i], delimiter='')


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

#ifdef LOCAL_DEBUG
#include "bits/mytest.h"
#endif

using namespace std;


 
class Solution{
#pragma region user
#define CLR(arr,val) fill(arr.begin(),arr.end(),val);
#define CLR0(arr)  CLR(arr,0)

#define d2clear(arr,data) for(int i =0;i<arr.size();i++){for(int j =0;j<arr[i].size();j++){arr[i][j]=data;}}
#define d2print(arr) for(int i =0;i<arr.size();i++){for(int j =0;j<arr[i].size();j++){cout<<arr[i][j];} cout<<endl;}
#define d2array(name,type,rows,cols,data) vector< vector<type>  > name(rows,vector<type>(cols,data))

#define FOR(i,N) for(auto i=0;i<N;i++)
#define RFOR(i,N) for(auto i=(N);i>=0;i--)
#define FORIT(arr,it) for(auto it=arr.begin();it!=arr.end();it++)
#define RFORIT(arr,it) for(auto it=arr.rbegin();it!=arr.rend();it++)

#define in(a,left,right) (a)<=(right)&&(a)>=(left)
#define notin(a,left,right) (a)<(left) && (a)>(right)

#define LL long long
#define A(n) n.begin(),n.end()
#define maxn(a,b) ((a)=((a)>(b)?(a):(b)))
#define minn(a,b) ((a)=((a)<(b)?(a):(b)))

#define min(a,b)  ( (a)<(b)?(a):(b)   )
#define max(a,b)  ( (a)>(b)?(a):(b)  )
#define println(a) cout<<a<<endl;
#define mp(a,b)  make_pair(a,b)
#pragma endregion
public:
	static const bool bMultiCase = false;
	void solve(istream & cin = std::cin, ostream & cout = std::cout){
		string s; cin >> s;
		int flag = 0;
		FOR(i, s.length()) {
			if (s[i] == 'C') {
				flag = 1;
			}
			if (flag == 1 && s[i] == 'F') {
				cout << "Yes" << endl; return;
			}
		}
		cout << "No" << endl;
	}

};


int main() {
#ifdef LOCAL_DEBUG 
 
	MyTest::Judge::JudgeNormal judge;
	MyTest::Config config;
	config.judge = &judge;
	MyTest::Test test(config);

	const string ITEM_NAME("1.cpp");
	const string FILE_NAME(__FILE__);
	auto it=FILE_NAME.find_last_of('\\');
	auto inputfile = FILE_NAME.substr(0, it + 1) + ITEM_NAME.substr(0, ITEM_NAME.find_last_of('.')) + "_input.txt";
	auto outputfile = FILE_NAME.substr(0, it + 1) + ITEM_NAME.substr(0, ITEM_NAME.find_last_of('.')) + "_output.txt";
	freopen(inputfile.c_str(), "r", stdin);
	//freopen(outputfile.c_str(), "w", stdout);
	
	while (test.ReadCaseInOneFile()) {
		test.Begin();
		Solution s;
		s.solve(test.Input(),test.Output());
		test.End();
	}
	test.DisplayInfo();
#else   //online judge
	if (Solution::bMultiCase) {
		int t; cin >> t;
		while (t--) {
			Solution s;
			s.solve();
		}
	}
	else {
		Solution s;
		s.solve();
	}
#endif
	

 
	return 0;
}

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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;
struct UnionFind {
    private:vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    public: int group_count;
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
        group_count=N;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        group_count--;
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    
};
double cal_dist(double x1,double x2,double y1,double y2,double z1,double z2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}


int main(){
    while(1){
    int n;
    cin>>n;
    if(n==0)break;

    double x[n],y[n],z[n],r[n];
    rep(i,n){
        double nz;
        cin>>x[i]>>y[i]>>z[i]>>r[i];
    }
    multimap<double,pair<int,int>>edge;
    UnionFind uf(n);
    for(int i=0;i<n;i++){
        for(int k=i+1;k<n;k++){
            
            double d=cal_dist(x[i],x[k],y[i],y[k],z[i],z[k]);
            if(d<=r[i]+r[k]){
                uf.unite(i,k);
            }
            else{
                d-=(r[i]+r[k]);
            edge.emplace(make_pair(d,make_pair(i,k)));
            }
        }
    }
    double ans=0;
    if(!edge.empty()){
        auto it=edge.begin();

        while(uf.group_count>1){
            int one=it->second.first;
            int two=it->second.second;
            if(!uf.same(one,two)){
                ans+=it->first;
            }
            uf.unite(one,two);
            it++;
        }
    }
        printf("%.3lf\n",ans);
    }

    


    return 0;

}
/*


*/



Measured memory_bytes: 3480
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,s,e) for(int i = s; i < e; i++)

bool cmp(string a, string b)
{
	return a < b;
}


string str[100001];
int main()
{
	int n;
	cin >> n;


	rep(i, 0, n)
	{
		cin >> str[i];
		sort(str[i].begin(), str[i].end());
	}
	sort(str, str + n, cmp);
	long long ans = 0;
	vector<int> num;
	num.push_back(0);
	int m = 1;
	rep(i, 0, n-1)
	{
		if (str[i] == str[i + 1])
		{
			ans += m;
			m++;
		}
		else
		{
			m = 1;
		}
	}

	cout << ans << endl;

}

Measured memory_bytes: 7296
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdio>
#include <numeric>

#define rep(i, n) for(int i = 0;i < (int)(n); i++)
#define pb push_back
typedef long long ll;

using namespace std;


int main() {
    ll n, k;
    cin >> n >> k;
    ll count = 0;
    ll bcNum1 = n / k;
    count += bcNum1 * bcNum1 * bcNum1;
    if(k % 2 == 0) {
        ll bcNum2 = (n + k / 2) / k;
        count += bcNum2 * bcNum2 * bcNum2;
    }
    cout << count<< endl;
    return 0;
}


Measured memory_bytes: 256
#import pysnooper
import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
from itertools import accumulate,combinations#,groupby,combinations_with_replacement
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)
input=stdin.readline

n=int(input().rstrip())
ans=10**9
if n&1:
    s,e=0,n
else:
    s,e=1,n-1
while s<=e:
    if s+e==n:
        now=0
        for i in str(s):
            now+=int(i)
        for i in str(e):
            now+=int(i)
        ans=min(ans,now)
    s+=1
    e-=1
print(ans)

Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
//for(int i = 0; i < n; i++)
 
int main() {
  int n, a, b, ans = 0, m1, d1, m2;
  //string s;
  cin >> n;
  cout << (n / 100 * 5 >= n % 100 || n >= 2000) << endl;
  //vector<int> v(n), c(n);
  //if(m1 != m2) {}
  //for(int i = 0; i < n; i++){}
}

Measured memory_bytes: 256
//#pragma GCC optimize("03", "unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR(i,n) for(i=0;i<n;i++)
#define FORn(i,j,n) for(i=j;i<n;i++)
#define pb push_back
#define unique_sort(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define vprint(v) for(auto t:v)cout<<t<<" "
#define endl "\n"

using namespace std;

typedef long long int lli;
typedef long int li;
typedef vector<lli> vli; 
typedef vector<int> vi; 
typedef vector<string> vs; 


const lli mod=1000000007;
const lli limit=1000000;


void fc(lli &x)
    {
        bool neg=false;
        register char c;
        x =0;
        c=getchar();
        if(c=='-')
        {
            neg = true;
            c=getchar();
        }
        for(;(c>47 && c<58);c=getchar())
            x = (x<<1) + (x<<3) +c -48;
        if(neg)
            x *=-1;
    }

int main() {

    fast()
    lli n,q,t;
    lli temp,temp1,temp2,temp3;
    lli i,j,k;
    map<string,lli> umap;
    string str;
    cin>>n;
    FOR(i,n){
        cin>>str;
        umap[str]++;
    }
    cout<<umap.size()<<endl;
 
}

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

using namespace std;

int main() {
  vector<int> A;
  A.reserve(100000);

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

  int M;
  int key;
  int sum = 0;

  cin >> M;
  for (int i = 0; i < M; i++) {
    cin >> key;
    //if (*lower_bound(A.begin(), A.end(), key) == key) {
    if (binary_search(A.begin(), A.end(), key)) {

      sum++;
    }
  }
  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 3124
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    int count = 0;
    for(int i = 0; i < S.length() - 1; i++) {
      if(S.charAt(i) != S.charAt(i + 1)) count++;
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 25044
#include <iostream>
#include <bits/stdc++.h>
const int Size = 200005;
long long Arr1[Size], Arr2[Size];
using namespace std;
int main()
{
    long long N,M,K;
    cin >> N >> M >> K;
    vector <long long> cumm1, cumm2;
    cumm1.push_back(0); cumm2.push_back(0);
    for (int i = 1; i <= N; i++){
        cin >> Arr1[i];
        cumm1.push_back(cumm1[i-1] + Arr1[i]);
    }
    for (int i = 1; i <= M; i++){
        cin >> Arr2[i];
        cumm2.push_back(cumm2[i-1] + Arr2[i]);
    }
    long long sum = 0;
    for (long long i = 0; i <= N; i++){
        if (K >= cumm1[i]){
            auto upper = upper_bound(cumm2.begin(), cumm2.end(), (K - cumm1[i]));
            long long idx = (upper - cumm2.begin()) - 1;
            sum = max(sum, idx + i);
        }
    }
    cout << sum ;
}


Measured memory_bytes: 10584
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m,k,ok;

signed main()
{

    cin>>n>>m;
    if(n == 1 || m == 1)
    {
        cout<<1<<endl;
    }
    else
    {
        cout<<(n*m+1)/2<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

constexpr int INF = 1 << 29;
constexpr int LIM = 405;

int N, Ma, Mb;
int A[40], B[40], C[40];

int mc[LIM][LIM];

using ll = long long;

int main() {
    cin >> N >> Ma >> Mb;
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i] >> C[i];
    }

    for (int i = 0; i < LIM; ++i) fill(mc[i], mc[i]+LIM, INF);

    mc[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int x = LIM-1; x >= A[i]; --x) {
            for (int y = LIM-1; y >= B[i]; --y) {
                mc[x][y] = min(mc[x][y], mc[x-A[i]][y-B[i]] + C[i]);
            }
        }
    }

    int ans = INF;
    for (int i = 1; max(Ma*i, Mb*i) < LIM; ++i) {
        ans = min(ans, mc[Ma*i][Mb*i]);
    }
    cout << (ans == INF ? -1 : ans) << endl;

    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(void){
    int n; cin>>n;
    vector <int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    multiset <int> se;
    se.insert(-114514);
    se.insert(a[0]);
    for(int i=1;i<n;i++){
        auto x = (--se.lower_bound(a[i]));
        if(*x== -114514) se.insert(a[i]);
        else{
            se.erase(x);
            se.insert(a[i]);
        }
    }
    cout<<se.size()-1<<endl;
}


Measured memory_bytes: 5760
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map(String::toInt)
    val b = readLine()!!.split(" ").map(String::toInt)
    val c = readLine()!!.split(" ").map(String::toInt)

    println(op140b(n, a, b, c))
}

fun op140b(
    n: Int,
    a: List<Int>,
    b: List<Int>,
    c: List<Int>
): Int {
    var sum = b.sum()
    a.forEachIndexed { index, i ->
        if (index == a.size - 1) return@forEachIndexed
        if (a[index + 1] - a[index] == 1) {
            sum += c[a[index]-1]
        }
    }
    return sum
}


Measured memory_bytes: 37992
#include <cstdio>
int main(){
 int d1,d2,d;
 while(true){
  scanf("%d %d",&d1,&d2);
  if ((d1==0) && (d2==0)) break;
  if (d1>d2) {
    d=d1; d1=d2; d2=d;
  }
  printf("%d %d\n",d1,d2);
 }
 return 0;
}

Measured memory_bytes: 1028
#include<bits/stdc++.h>
using namespace std;
set<int> a, b;
int main()
{
	int n, m;
	scanf("%d",&n);
	int i;
	for(i=0; i<n; i++)
	{
		int x;
		scanf("%d",&x);
		a.insert(x);
	}
	scanf("%d",&m);
	for(i=0; i<m; i++) 
	{
		int x;
		scanf("%d",&x);
		b.insert(x);
	}
	vector<int> v;
	set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(v));
	for(i=0; i<v.size(); i++) printf("%d\n",v[i]);
	return 0;
}


Measured memory_bytes: 22060
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
   int a,b,c;
   cin>>a>>b>>c;
   if((a==b&&a!=c)||(a==c&&a!=b)||(b==c&&a!=b))
     cout<<"Yes"<<endl;
   else
     cout<<"No"<<endl;
}

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

int main(){

    int N;
    std::cin >> N;
    std::vector<int> costs;

    for(int cost; std::cin >> cost;){
        costs.push_back(cost);
    }

    std::vector<int> dp_cost_min(1,0); //初期の足場コストは0
    dp_cost_min.push_back(std::abs(costs.at(1) - costs.at(0)));   //二番目の足場コストは一意 

    // 遷移式 
    for(int i = 2; i < N;++i){
        int dp1 = dp_cost_min.at(i-1) + std::abs(costs.at(i) - costs.at(i-1));
        int dp2 = dp_cost_min.at(i-2) + std::abs(costs.at(i) - costs.at(i-2));
        int dp_min = std::min(dp1,dp2);
        dp_cost_min.push_back(dp_min);
    }

    std::cout << dp_cost_min.at(N-1) <<std::endl;
}

Measured memory_bytes: 4272
import Data.List

main :: IO ()
main = do
    [a,b,k] <- map read . words <$> getLine :: IO [Int]
    let g = gcd a b
        a' = [ i | i <- [1..g], (a `mod` i) == 0]
        b' = [ i | i <- [1..g], (b `mod` i) == 0]
        c  = intersect a' b'
    print $ c !! (length c - k)


Measured memory_bytes: 636
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n,P=0,N=0; cin>>n;
    vector<int> a(n,0);
    rep(i,n){
        cin>>a[i];
        if(a[i]>=0) P++;
        else N++;
    }
    sort(al(a)); reverse(al(a));
    if(N==n){
        N--; P++;
    }
    else if(P==n){
        N++; P--;
    }
    int ans=0;
    rep(i,n){
        if(i<P) ans+=a[i];
        else ans-=a[i];
    }
    cout<<ans<<endl;
    int cur=a[P];
    rep(i,P-1){
        cout<<cur<<" "<<a[i+1]<<endl;
        cur-=a[i+1];
    }
    cout<<a[0]<<" "<<cur<<endl;
    cur=a[0]-cur;
    rep(i,N-1){
        cout<<cur<<" "<<a[P+1+i]<<endl;
        cur-=a[P+1+i];
    }
}


Measured memory_bytes: 2304
import sys
sys.setrecursionlimit(5000)

def dfs(x):
    global ng, parity
    for v in adj[x]:
        if parity[v] == parity[x]:
            ng = True
            return
        elif parity[v] < 0:
            parity[v] = 1^parity[x]
            dfs(v)
    return

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    adj = [[] for _ in range(n)]
    parity = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
    ng = False
    parity[0] = 0
    dfs(0)
    if ng:
        print(0)
        continue
    ans = []
    zero = parity.count(0)
    if zero%2 == 0:
        ans.append(zero//2)
    if (n-zero)%2 == 0 and zero*2 != n:
        ans.append((n-zero)//2)
    ans.sort()
    print(len(ans))
    if ans:
        print(*ans, sep="\n")


Measured memory_bytes: 5996
#include <stdio.h>
int main(){
    int a[33]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int n;
    scanf("%d", &n);
    printf("%d", a[n-1]);
}

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

#define endl '\n'

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

    double l; cin >> l;
    double f = l/3;

    cout << fixed << setprecision(12) << f*f*f << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
mod = 10**9 + 7

memo = [{} for i in range(N+1)]

def judge(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1],t[i] = t[i],t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True
    
def dfs(i,last3):
    if last3 in memo[i]:
        return memo[i][last3]
    if i == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if judge(last3+c):
            ret = (ret + dfs(i+1,last3[1:]+c))%mod
    memo[i][last3] = ret
    return ret

print(dfs(0,'TTT'))

Measured memory_bytes: 3872
class uni:
    def __init__(self,n):
        self.n = n
        self.pare = [i for i in range(n)]
        self.rank = [0]*n

    def find(self,x):
        if self.pare[x] == x:
            return x
        else:
            self.pare[x] = self.find(self.pare[x])
            return self.pare[x]

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.pare[x] = y
        else:
            self.pare[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def show(self):
        return self.pare


N, M, K = map(int,input().split())
size = [0]*N
count = [0]*N
side = [[]for i in range(N)]
union = uni(N)
for i in range(M):
    a,b = map(int,input().split())
    union.union(a-1,b-1)
    count[a-1] += 1
    count[b-1] += 1
for i in range(N):
    size[union.find(i)] += 1
for i in range(K):
    c,d = map(int,input().split())
    if union.pare[c-1] == union.pare[d-1]:
        count[c-1] += 1
        count[d-1] += 1
for i in range(N):
    print(size[union.pare[i]]-count[i]-1,end=" ")
print()

Measured memory_bytes: 92832