akhauriyash/Code-Regression huggingface dataset:
n, w = map(int, input().split())
item = [list(map(int, input().split())) for i in range(n)]

max_v = 100005

dp = [[float('inf')] * max_v for j in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for sum_v in range(max_v):
        if sum_v - item[i][1] >= 0:
            dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - item[i][1]] + item[i][0])
        dp[i + 1][sum_v] = min((dp[i + 1][sum_v], dp[i][sum_v]))

for sum_v in reversed(range(max_v)):
    if dp[-1][sum_v] <= w:
        print(sum_v)
        break


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

int main() {
  string s;cin >> s;
  reverse(s.begin(),s.end());
  vector<string> v = {"maerd","remaerd","esare","resare"};

  string t = "";
  rep(i,s.size()){
    t.push_back(s.at(i));
    if( count(v.begin(),v.end(),t) ) t = "";
  }
  if( t == "" )
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3996
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>

using namespace std;

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

#define fi first
#define se second

typedef pair<int,int> pii;

int h,w;
int n;
int m;
vector<pii> pos;
vector<pii> hoge;

bool input(){
	cin>>w>>h;
	if(w==0)return false;
	cin>>n;
	pos.resize(n);
	rep(i,n){
		cin>>pos[i].fi>>pos[i].se;
		pos[i].fi--;
		pos[i].se--;
	}
	cin>>m;
	hoge.resize(m);
	rep(i,m){
		cin>>hoge[i].fi>>hoge[i].se;
		hoge[i].fi--;
		hoge[i].se--;
	}
	return true;
}

int dist(pii a, pii b){
	
	a.fi += -(a.se)/2;
	b.fi += -(b.se)/2;
	
	if(a.se > b.se)swap(a,b);
	
	b.fi -= a.fi;
	b.se -= a.se;
	
	int ret = 0;
	if(b.fi >= 0){
		ret = b.fi + b.se;
	}else if(b.se >= -b.fi){
		ret = b.se;
	}else{
		ret = -b.fi;
	}
	
	
	return ret;
}

int solve2(int x,int y){
	
	int ret = 0;
	vector<pii> cand = pos;
	cand.push_back(pii(x,y));
	
	rep(i,h){
		rep(j,w){
			const int INF = 1111;
			int cnt = 0;
			int mini = INF;
			int minp = -1;
			rep(k, cand.size()){
				int d = dist(pii(j,i), cand[k]);
				
				if(d==mini){
					cnt++;
				}
				if(d<mini){
					cnt = 1;
					mini = d;
					minp = k;
				}
			}
			
			if(cnt==1 && minp==pos.size()){
				ret++;
			}
		}
	}
	return ret;
}

int solve(){
	int ret = 0;
	
	rep(i,m){
		
		int val = solve2(hoge[i].fi,hoge[i].se);
		ret = max(ret, val);
	}
	
	return ret;
}

void call(){
	cout<<solve()<<endl;
}

int main(){
	while(input())call();
}

Measured memory_bytes: 1200
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  ll N;
  cin >> N;
  umll A;
  REP(i, 1, N+1) {
    ll a;
    cin >> a;
    A.emplace(a, i);
  }

  cout << A[1];
  REP(i, 2, N+1) {
    cout << " " << A[i];
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 4900
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int64_t INF = 1LL << 60;


int main() {
 string s;
 cin>>s;
 int count =0;
 for(int i=0;i<s.size();i++){
     if(i+1<s.size()&&s[i+1]!=s[i]){count++;}
 }
 cout<<count<<endl;
 return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;

int main() {
    int N, cnt;
    cin >> N;
    vector<i_i> towns(N, {0, 0});
    vector<int> array;
    double total, ans;

    rep(i, N){
        int x,y;
        cin >> x >> y;
        towns[i] = {x, y};
        array.push_back(i + 1);
    }

    total = 0;
    cnt = 0;
    do{
        for(int i = 0; i < N - 1; i++){
            total += sqrt(pow(towns[array[i] - 1].first - towns[array[i + 1] - 1].first , 2.0) + pow(towns[array[i] - 1].second - towns[array[i + 1] - 1].second, 2.0));
        }
        cnt++;
    }while(next_permutation(array.begin(), array.end()));


    ans = total / cnt;
    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}


Measured memory_bytes: 256
# A - HonestOrDishonest
def main():
    a, b = input().split()

    if a == 'H':
        if b == 'H':
            print('H')
        else:
            print('D')
    else:
        if b == 'H':
            print('D')
        else:
            print('H')
  
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 8832
s = input()

import itertools
n = list(itertools.product([0,1], repeat=len(s)-1))

int_list = []
for x in n:
    start = 0
    end = 1
    for y in x:
        if y == 1:
            end+=1
        else:
            int_list.append(int(s[start:end]))
            start=end
            end+=1
    int_list.append(int(s[start:end]))
    
print(sum(int_list))

Measured memory_bytes: 3064
using System;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            if (S[0] == S[1] && S[2] == S[3] && S[0] != S[2])
            {
                Console.WriteLine("Yes");
                return;
            }
            if (S[0] == S[2] && S[1] == S[3] && S[0] != S[1])
            {
                Console.WriteLine("Yes");
                return;
            }
            if (S[0] == S[3] && S[1] == S[2] && S[0] != S[1])
            {
                Console.WriteLine("Yes");
                return;
            }
            Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 11092
#include<iostream>
using namespace std;
//int gcd(int x, int y) {
//	if (y == 0)return x;
//	return gcd(y, x%y);
//}
//int main() {
//	int x, y;
//	cin >> x >> y;
//	cout << gcd(x, y) << endl;
//	return 0;
//}
int main() {
	int x, y,q,r; cin >> x >> y;
	if (y > x)swap(x, y);
	while (y>0) {
		r = x%y;
		x = y;
		y = r;
	}
	cout << x << endl;
	return 0;
}

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

int A,B,C,D;

signed main() {
  cin >> A >> B >> C >> D;
  
  while(true) {
    C-=B;
    if(C<=0) {
      puts("Yes");
      return 0;
    }
    A-=D;
    if(A<=0) {
      puts("No");
      return 0;
    }
  }
}


Measured memory_bytes: 3624
#pragma warning(disable:4996)
#include <stdio.h>

int main() {
	int w, h;
	int x, y;
	scanf("%d %d %d %d", &w, &h, &x, &y);

	printf("%lf %d\n", (double)w * (double)h / 2, x + x == w && y + y == h);
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map>

using namespace std;

using ll = long long;
using ui = unsigned int;
const ll MOD = 1000000007;
const ll INF = 9223372036854775807;

//ARC100-C
int main() {
	ll N;
	scanf("%lld", &N);
	vector<ll> A(N, 0);
	for (ll i = 0; i < N; i++) {
		scanf("%lld", &A[i]);
	}

	vector<ll> B(N, 0);
	ll sum = 0;
	for (ll i = 0; i < N; i++) {
		B[i] = A[i] - (i + 1);
	}

	std::sort(B.begin(), B.end());

	ll b = B[N / 2];


	ll result = 0;

	for (ll i = 0; i < N; i++) {
		result += std::abs(A[i] - (b + i + 1));
	}

	printf("%lld\n", result);

}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;

int main() {
    ll Q, H, S, D, N;
    ll m;
    ll ans = 0;
    ll count;

    cin >> Q >> H >> S >> D;
    cin >> N;

    m = min({8*Q, 4*H, 2*S, D});
    count = N / 2;
    ans += count * m;
    N -= (N/2) * 2;

    m = min({4*Q, 2*H, S});
    count = N / 1;
    ans += count * m;
    N -= (N/1);

    m = min({2*Q, H});
    count = N / 0.5;
    ans += count * m;
    N -= (N/0.5);

    m = Q;
    count = N / 0.25;
    ans += count * m;
    N -= (N/0.25);


    cout << ans << endl;
}


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1e9+7;
constexpr ll inf = ((1<<30)-1)*2+1 ;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,k = 0;;
  cin >> n;
  vector<ll> t(n),a(n);
  bool f = false;
  rep(i,n){
    cin >> t[i];
    if(k > t[i]){
      f = true;
    }
    k = t[i];
  }
  k = inf;
  rep(i,n){
    cin >> a[i];
    if(k < a[i]){
      f = true;
    }
    k = a[i];
  }
  ll ans = 1,T = *max_element(all(t)),A = *max_element(all(a));
  if(f || T != A){
    cout << 0 << endl;
    return 0;
  }
  vector<ll> h(n,0);
  rep(i,n){
    if(i == 0 || t[i - 1] < t[i]){
      h[i] = t[i];
    }
  }
  rep(i,n){
    if(i == 0 || a[n - i] < a[n-1-i]){
      h[n-i-1] = max(h[n-i-1],a[n - i - 1]);
    }
  }
  rep(i,n){
    if(h[i] < t[i] && h[i] < a[i]){
      ans = ans * min(t[i],a[i]) % mod;
    }
    if(h[i] == t[i] && h[i] > a[i]){
      ans = 0;
    }
    else if(h[i] == a[i] && h[i] > t[i]){
      ans = 0;
    }
  }
  cout << ans % mod << endl;
  return 0;
}



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

int main() {
    string S;
    cin >> S;
    int size = S.size();
    bool isEasy = true;
    rep(i,size) {
        if (i % 2 == 1) {
            if (S[i] == 'R') isEasy = false;
        }
        else if (S[i] == 'L') isEasy = false;
    }
    if (!isEasy) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 256
// Problem : B - 123 Triangle
// Contest : AtCoder - AtCoder Grand Contest 043
// URL : https://atcoder.jp/contests/agc043/tasks/agc043_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

void doOnce(const vector<int>& a, vector<int>& v) {
	for (int i = 0; i < a.size() - 1; i++) {
		v[i] = abs(a[i] - a[i + 1]);
	}
}

void computeTwos(vector<int>& twos) {
	int n = twos.size();
	for (int i = 2; i < n; i *= 2) {
		for (int j = i; j < n; j += i) {
			twos[j]++;
		}
	}
	for (int i = 1; i < n; i++) {
		twos[i] += twos[i - 1];
	}
}

int main() {
	int N;
	cin >> N;
	string s;
	cin >> s;
	vector<int> a(N);
	for (int i = 0; i < N; i++) {
		a[i] = s[i] - '0';
	}
	vector<int> v(N - 1);
	doOnce(a, v);
	
	vector<int> twos(N + 1);
	computeTwos(twos);
	
	auto chooseOdd = [&](int n) {
		return twos[N - 2] - twos[n] - twos[N - 2 - n] == 0;
	};
	
	auto getXored = [&](int d) {
		int xored = 0;
		for (int i = 0; i < N - 1; i++) {
			if (chooseOdd(i)) {
				xored ^= v[i]/d;
			} else {
				xored ^= 0;
			}
		}
		return xored;
	};
	
	if (getXored(1) & 1) {
		cout << "1\n";
		return 0;
	}
	
	for (int i = 0; i < N - 1; i++) {
		if (v[i] == 1) {
			cout << "0\n";
			return 0;
		}
	}
	
	if (getXored(2) & 1) {
		cout << "2\n";
	} else {
		cout << "0\n";
	}
}


























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

int main(){
  string s,r,a="AIDUNYAN";
  cin >> s;r=s;
  int c[26]={},z=0;
  for(char k:a)c[k-'A']--;
  for(int i=0;i<s.size();i++){
    if(i>7){
      if(!c[s[i-8]-'A'])z--;
      if(--c[s[i-8]-'A']==0)z++;
    }
    if(!c[s[i]-'A'])z--;
    if(++c[s[i]-'A']==0)z++;
    if(z==6){for(int j=0;j<8;j++)r[i-7+j]=a[j];r[i-5]='Z';}
  }
  cout << r << endl;
}

Measured memory_bytes: 1196
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		ArrayList<String> s = nextCharArray();
		int c = 0;
		int output = s.size();
		for(int i = 0; i < s.size(); i++){
			if(s.get(i).equals("S")){
				c++;
			}else{
				if(c > 0){
					c--;
					output -= 2;
				}
			}
		}
		myout(output);

	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 50608
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
const long long INF = 1LL << 60;
typedef long long ll;
int main() {
    ll X,Y;
    cin >> X >> Y;
    int cnt=0;
    ll A = X;
    while(A <= Y){
        cnt++;
        A = 2*A;
    }
    cout << cnt << endl;
}

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

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int m,n;
    cin>>m>>n;
    
    int a[m][n];
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            cin>>a[i][j];
        }
    }
    int b[n];
    for(int i=0; i<n; i++) cin>>b[i];

    
    for(int i=0; i<m; i++){
        int sum = 0;
        for(int j=0; j<n; j++){
            sum += a[i][j]*b[j];            
        }
        cout<<sum<<endl;
    }
}


Measured memory_bytes: 3212
// https://atcoder.jp/contests/abc103/tasks/abc103_c

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

ll N, a, r = 0;
int main()
{
  cin >> N;
  REP(i, N)
  {
    cin >> a;
    r += (a - 1);
  }

  cout << r << '\n';
  return 0;
}


Measured memory_bytes: 256
n, d = list(map(int, input().split()))
arr = [list(map(int, input().split())) for _ in range(n)]
ans = 0

def calc(x, y):
    return (x ** 2 + y ** 2) ** 0.5

for x, y in arr:
    if d >= calc(x, y):
        ans += 1
print(ans)


Measured memory_bytes: 45564
#include <iostream>
#include <queue>

using namespace std;

char mp[1002][1002];
int n,m;
string str;
struct node{
    int x;
    int y;
    int step;
};
int tox[] = {-1,0,0,1};
int toy[] = {0,-1,1,0};
bool vis[1002][1002];
int cnt,cnt2,cnt3;

int main()
{
    queue<node> q;
    node s;
    cin >> n >> m;
    for(int i = 0;i < n;i++)
    {
        cin >> str;
        for(int j = 0;j < m;j++)
        {
            mp[i][j] = str[j];
            if(str[j]  == '.')cnt++;
            else{s.x = i,s.y = j;
                q.push(s);
                cnt2++;
            }
        }
    }
    node no;
    int ans = 0;
    while(cnt)
    {
        ans++;
        while(cnt2--)
        {
            no = q.front();
            q.pop();
            for(int i = 0;i < 4;i++)
            {
                int x = no.x + tox[i];
                int y = no.y + toy[i];
                if(x>=0&&y>=0&&x<n&&y<m&&mp[x][y] == '.' && vis[x][y] == 0){
                    cnt--;
                    vis[x][y] = 1;
                    s.x = x;
                    s.y = y;
                    q.push(s);
                    cnt3++;
                }
            }
        }
        cnt2 = cnt3;
        cnt3 = 0;
    }
    cout << ans << endl;
    return 0;
}


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

forward = 0
backward = N-1

sum = list[forward]
sum2 = list[backward]
while (True):
    if backward - forward == 1:
        break
    if sum < sum2:
        forward += 1
        sum += list[forward]
    else:
        backward -= 1
        sum2 += list[backward]
print(abs(sum - sum2))

Measured memory_bytes: 26396
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	static Deque<Point> que;
	static Deque<Point> cornerque;
	static int[][] warpcnt;
	static boolean[][] map;
	static int H;
	static int W;

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			H = sc.nextInt();
			W = sc.nextInt();
			warpcnt = new int[H][W];
			int CH = sc.nextInt() - 1;
			int CW = sc.nextInt() - 1;
			int DH = sc.nextInt() - 1;
			int DW = sc.nextInt() - 1;
			map = new boolean[H][W];
			for (int i = 0; i < H; i++) {
				String line = sc.next();
				for (int j = 0; j < W; j++) {
					map[i][j] = line.charAt(j) == '.';
					warpcnt[i][j] = -1;
				}
			}
			que = new ArrayDeque<>();
			cornerque = new ArrayDeque<>();
			warpcnt[CH][CW] = 0;
			Point C = new Point(CH, CW);
			que.add(C);
			while (!que.isEmpty()) {
				while (!que.isEmpty()) {
					Point tmp = que.remove();
					boolean up = move(tmp, 0, -1, 0);
					boolean down = move(tmp, 0, 1, 0);
					boolean left = move(tmp, 0, 0, -1);
					boolean right = move(tmp, 0, 0, 1);
					if (!up || !down || !left || !right) {
						cornerque.add(tmp);
					}
				}
				while (!cornerque.isEmpty()) {
					Point tmp = cornerque.remove();
					move(tmp, 1, -2, -1);
					move(tmp, 1, -2, 1);
					move(tmp, 1, -2, 0);
					move(tmp, 1, 2, -1);
					move(tmp, 1, 2, 0);
					move(tmp, 1, 2, 1);
					move(tmp, 1, -1, -2);
					move(tmp, 1, 0, -2);
					move(tmp, 1, 1, -2);
					move(tmp, 1, -1, 2);
					move(tmp, 1, 0, 2);
					move(tmp, 1, 1, 2);
					move(tmp, 1, -1, -1);
					move(tmp, 1, -2, -2);
					move(tmp, 1, -1, 1);
					move(tmp, 1, -2, 2);
					move(tmp, 1, 1, -1);
					move(tmp, 1, 2, -2);
					move(tmp, 1, 1, 1);
					move(tmp, 1, 2, 2);
				}
			}
			System.out.println(warpcnt[DH][DW]);
		}
	}

	static boolean move(Point p, int warp, int h, int w) {
		if (p.h + h < 0 || p.w + w < 0 || p.h + h >= H || p.w + w >= W) {
			// do nothing
			return false;
		}
		if (map[p.h + h][p.w + w]) {
			int wcnt = warpcnt[p.h + h][p.w + w];
			int nowcnt = warpcnt[p.h][p.w] + warp;
			if (wcnt == -1) {
				warpcnt[p.h + h][p.w + w] = nowcnt;
				if (warp == 0) {
					que.addFirst(new Point(p.h + h, p.w + w));
				} else {
					que.add(new Point(p.h + h, p.w + w));
				}
				return true;
			} else if (wcnt > nowcnt) {
				warpcnt[p.h + h][p.w + w] = nowcnt;
				if (warp == 0) {
					que.addFirst(new Point(p.h + h, p.w + w));
				} else {
					que.add(new Point(p.h + h, p.w + w));
				}
				return true;
			}
		}
		return false;
	}

	static class Point {
		int h;
		int w;
		int warp;

		public Point(int h, int w) {
			this.h = h;
			this.w = w;
			this.warp = 0;
		}
	}
}

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

using namespace std;

int main(){
    int  n;
    while(cin>>n,n){
        vector<int>students(n);
        for(int i=0;i<n;++i){
            cin>>students[i];
        }
        sort(students.begin(),students.end());
        int ans=100000000;
        for(int i=1;i<n;++i){
            ans=min(ans,students[i]-students[i-1]);
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 3048
MOD = 10**9+7
H, W = map(int, input().split(' '))
map_info = [input() for i in range(H)]

path_pattern = [[0 for i in range(W)] for j in range(H)]

for width in range(W):
    if map_info[0][width] == '.':
        path_pattern[0][width] = 1
    else:
        break
for height in range(H):
    if map_info[height][0] == '.':
        path_pattern[height][0] = 1
    else:
        break
for height in range(1, H):
    for width in range(1, W):
        if map_info[height][width] == '.':
            temp = (path_pattern[height-1][width]
                    + path_pattern[height][width-1]) \
                    % MOD
            path_pattern[height][width] = temp
        else:
            pass

print(path_pattern[-1][-1])


Measured memory_bytes: 44636
#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long ll;
ll dp[66][2][2];
const ll mod=1e9+7;
ll L,R;
ll dfs(int u,bool Lt,bool Rt,bool zero) {
    if(u<0) return 1;
    if(dp[u][Lt][Rt]>=0&&!zero) return dp[u][Lt][Rt];
    ll ans=0;
    int l=0,r=1;
    if(Lt) l=L>>u&1;
    if(Rt) r=R>>u&1;
    for(int i=l;i<=1;i++) for(int j=i;j<=r;j++) {
        if(j==1&&zero) {
            if(i==1) ans+=dfs(u-1,Lt&&i==l,Rt&&j==r,zero&&j==0);
        }
        else {
            ans+=dfs(u-1,Lt&&i==l,Rt&&j==r,zero&&j==0);
        }
    }
    ans%=mod;
    if(!zero) {
        dp[u][Lt][Rt]=ans;
    }
    return ans;
}
int main() {
    scanf("%lld%lld",&L,&R);
    memset(dp,-1,sizeof(dp));
    printf("%lld\n",dfs(62,1,1,1));
    return 0;
}


Measured memory_bytes: 256
nums = int(input())
ary = list(map(int, input().split()))
parity = [0,0]

# 奇数、偶数の数をとる
for i in ary:
    if   i % 2 == 0:
        parity[0] += 1
    elif i % 2 == 1:
        parity[1] += 1

while not parity[0] + parity[1] <= 2:
    if parity[0] >= 2:
        parity[0] -= 2
        parity[0] += 1
    elif parity [1] >= 2:
        parity[1] -= 2
        parity[0] += 1
if parity[0] == 2 or parity[1] == 2:
    print("YES")
else:
    print("NO")

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

namespace AtTest.Dwango6_prelims
{
    class A
    {
        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);

            Method(args);

            Out.Flush();
        }

        static void Method(string[] args)
        {
            int n = ReadInt();
            string[] ss = new string[n];
            int[] ts = new int[n];
            for(int i = 0; i < n; i++)
            {
                string[] vals = Read().Split();
                ss[i] = vals[0];
                ts[i] = int.Parse(vals[1]);
            }
            string x = Read();
            bool after = false;
            int res = 0;
            for(int i = 0; i < n; i++)
            {
                if (after) res += ts[i];
                else if (ss[i].Equals(x)) after = true;
            }
            WriteLine(res);
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 13140
#include "bits/stdc++.h"
using namespace std;
#define INF 1e9
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,l,r) for(int i=(l);i<(r);i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
const long long mod = 1e9+7;
typedef long long ll;  //ll とdoubleは違う
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<bool> VB;
typedef vector<int> VI;  // VI a(n);
typedef vector<double> VD;  
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VII;   // VII a(n,vector<int>(m)) n * m 
typedef vector<VL> VLL;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<ll, ll> > PS;
template <class T, class U>  // chmax(max, a);
bool chmax(T &a, U b){
    if (a < b){ a = b;return 1;}
    return 0;
}
template <class T, class U> //chmin(min,a)
bool chmin(T &a, U b){
    if (a > b){ a = b; return 1;}
    return 0;
}
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
// g++ -std=c++11 prac.cpp 

int main(){
    ll a,b,x=0,y=0,z=0,n,m=0,k,ans=0,h,w,sum=0,Max=-1e9-1,cnt=0,Min=1e9+1;
    string s,t,u;
    bool ok=true;
    cin >> a >> b >> k;
    if(k >= a){
        x = a;
        a = 0;
        if(b >= k-x)
            b -= (k-x);
        else
            b = 0;
    }
    else{
        a = a-k;
        cout << a << " " << b << endl;
        return 0;
    }
    cout << a << " " << b << endl;
    return 0;
}


 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#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;}

const int mod = 1e9+7;
const int M = 13;

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

    int n = s.size();

    int dp[M] = {};
    dp[0] = 1;

    rep(i,n){
        int l = 0, r = 10;
        if(s[i] != '?'){
            l = s[i]-'0';
            r = l+1;
        }

        int nx[M] = {};
        for(int j=l; j<r; ++j){
            rep(k,M){
                int a = (k*10+j)%M;
                (nx[a] += dp[k]) %= mod;
            }
        }

        rep(j,M) dp[j] = nx[j];
    }

    cout << dp[5] << endl;
    return 0;
}


Measured memory_bytes: 512
#include<iostream>

using namespace std;
int main(){
  int xa,ya,xb,yb;
  cin>>xa>>ya>>xb>>yb;
  int dx=xb-xa;
  int dy=yb-ya;
  int xc=xb-dy;
  int yc=yb+dx;
  int xd=xa-dy;
  int yd=ya+dx;
  cout<<xc<<' '<<yc<<' '<<xd<<' '<<yd<<endl;
}

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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define V vector<int>
#define M map<int,int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int,V,greater<int>>

#define pb(a) push_back(a)
#define mp make_pair

#define dump(x)  cout << #x << " = " << (x) << "\n";
#define COUT(x) cout<<(x)<<"\n"
ll memo[100] = {};

ll LucasNumber(int x)
{
    if (x == 0)
    {
        return 2;
    }
    if (x == 1)
    {
        return 1;
    }

    if (memo[x] != 0)
    {
        return memo[x];
    }

    return memo[x] = LucasNumber(x - 1) + LucasNumber(x - 2);
}


int main()
{
    int x = 0;
    cin >> x;
    ll num = LucasNumber(x);
    COUT(num);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N; cin >> N;
  string S; cin >> S;
  int cnt = 0;
  
  for(int i = 0; i < 10; ++i){
    for(int j = 0; j < 10; ++j){
      for(int k = 0; k < 10; ++k){
        string a = to_string(i);
        string b = to_string(j);
        string c = to_string(k);
        string abc = a + b + c;
        bool ac = false;
        bool bc = false;
        for(int l = 0; l < S.size(); ++l){
          if(abc.at(0) == S.at(l) && !ac && !bc){
            ac = true;
            continue;
          }
          if(abc.at(1) == S.at(l) && ac && !bc){
            bc = true;
            continue;
          }
          if(abc.at(2) == S.at(l) && ac && bc){
            cnt++;
            break;
          }
        }
      }
    }
  }
  
  cout << cnt << endl;
}

Measured memory_bytes: 384
#coding:utf-8
import sys
import bisect
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = II()
    L = LMIIS()
    L.sort()
    count = 0
    for i in range(N):
        a = L[i]
        k = i+2
        for j in range(i+1,N):
            b = L[j]
            while k < N and a+b > L[k]:
                k += 1
            count += k - 1 - j
    print(count)



if __name__ == '__main__':
    main()

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

int n, k;
int a[100010];
long long int p[100010];
long long int m[100010];

int main() {

	cin >> n >> k;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		p[i] = p[i-1] + a[i];
		m[i] = m[i-1];
		if (a[i] > 0) m[i] += a[i];
	}
	
	long long int maxi = 0;
	for (int i = k; i <= n; i ++) {
		long long int tren = m[n] - m[i];
		tren += m[i-k];
		long long int zbr = p[i] - p[i-k];
		tren = max(tren, tren+zbr);
		
		maxi = max(maxi, tren);
	}

	cout << maxi;

	return 0;
}


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

using namespace std;

int main() {
  int x, y;
  cin >> x >> y;
  if(y % 2 == 1) {
    cout << "No" << endl;
    return 0;
  }
  if(y > 4 * x || y < 2 * x) {
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    int n; cin>>n;
    vector<int> v(n), c(n);
    for(int i=0; i<n; i++) cin>>v[i];
    for(int i=0; i<n; i++) cin>>c[i];

    ll ans = 0;
    for(int bit=0; bit<(1<<n); bit++){
        ll X = 0;
        for(int i=0; i<n; i++){
            if(bit & (1 << i)){
                X += v[i];
                X -= c[i];
            }
        }

        chmax(ans, X);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include "iostream"
#include <iomanip>
#include "math.h"
using namespace std;
 
int main(){
 
  int A,B;
  double H,M;
  double angA,angB,ang,ans;
  
  cin >> A >> B >> H >> M;
  
  angA = H/6 + M/360;
  angB = M/30;
  
  ang = abs(angA - angB) * 3.1415926535898;
   
  ans = pow(A*A+B*B-2*A*B*cos(ang),0.5);
  
    cout << setprecision(17)<< ans;
    
  return 0;
  
}

Measured memory_bytes: 4348
#include<bits/stdc++.h> 
#define ll long long
#define pb push_back
#define ld double
using namespace std;

ld dp[312][312][312];


int main(){
 
    int n;
    cin >> n;
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == 1) {
            c1++;
        } else if (x == 2) {
            c2++;
        } else {
            c3++;
        }
    }
 
    for (int k = 0; k < 307; k++) {
        for (int j = 0; j + k < 307; j++) {
            for (int i = 0; i + j + k < 307; i++) {
                if (i == 0 && j == 0 && k == 0) {
                    continue;
                }
                if (i + j + k > 307) {
                    continue;
                }
                ld wait = 1.0 * n / (i + j + k);
                ld pi = 1.0 * i / (i + j + k);
                ld pj = 1.0 * j / (i + j + k);
                ld pk = 1.0 * k / (i + j + k);
 
                if (i) {
                    dp[i][j][k] += pi * dp[i - 1][j][k];
                }
                if (j) {
                    dp[i][j][k] += pj * dp[i + 1][j - 1][k];
                }
                if (k) {
                    dp[i][j][k] += pk * dp[i][j + 1][k - 1];
                }
                dp[i][j][k] += wait;
            }
        }
    }
 
    cout.precision(10);
    cout << fixed << dp[c1][c2][c3] << "\n";
  
return 0;
}

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

int n, ans;

bool is753 (int x) {
    bool is7 = false, is5 = false, is3 = false;
    while (x) {
        int num = x % 10;
        if (num == 7) is7 = true;
        else if (num == 5) is5 = true;
        else if (num == 3) is3 = true;
        else return false;
        x /= 10;
    }
    return is7 && is5 && is3;
}

int main() {
    cin >> n;
    int size = min(n, 777777753);
    for (int i = 357; i <= size; i += 2) {
        if (is753(i)) ans++;
        if (i /  10000000 == 1) i +=  (20000000 - 2);
        if (i /  10000000 == 4) i +=  (10000000 - 2);
        if (i /  10000000 == 6) i +=  (10000000 - 2);
        if (i /  10000000 == 8) i  =  333333355;
        if (i / 100000000 == 4) i += (100000000 - 2);
        if (i / 100000000 == 6) i += (100000000 - 2);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ar array
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> q;
  while(q--){
    ll a, b;
    cin >> a >> b;
    if(a>b)
      swap(a, b);
    if(a==b||a+1==b){
      cout << 2*a-2 << '\n';
      continue;
    }
    a*=b;
    ll x = sqrtl(a);
    if(x*x==a)
      x--;
    if(x*(x+1)<a){
      cout << 2*x-1 << '\n';
    }
    else{
      cout << 2*x-2 << '\n';
    }
  }
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	int N, M;
	int[] X;
	void Solve()
	{
		var I = G;
		N = I[0]; M = I[1];
		X = G;
		Array.Sort(X);
		var d = new List<int>();
		for (var i = 1; i < M; i++) d.Add(X[i] - X[i - 1]);
		d.Sort();
		WriteLine(d.Take(M - N).Sum());
	}
}


Measured memory_bytes: 19296
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <bitset>
#include <utility>
#include <complex>
#include <assert.h>
#include <limits.h>
//#include <bits/stdc++.h>
using namespace std;
#define rank rankk
#define mp make_pair
#define pb push_back
#define xo(a,b) ((b)&1?(a):0)
#define tm tmp

//#define LL ll
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,ll>pil;
typedef pair<ll,ll> pll;
//const double INF=1e20;
const int INF=0x3f3f3f3f;
//const int INF= 0x7fffffff;
//const ll INF=0x3f3f3f3f3f3f3f3fll;
//const ll INFF=0x3f3f3f3f3f3f3fll;
//const ll INFF=1e14+5;
const int MAX=3e5+5;
//const ll MAXN=2e8;
//const int MAX_N=MAX;
//const ll MOD=1e9+7;
const int MOD=1e9+7;
//const long double pi=acos(-1.0);
//const double eps=0.00000001;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
template<typename T>inline T abs(T a) {return a>0?a:-a;}
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
inline ll powMM(ll a,ll b,ll M){
    ll ret=1;
    a%=M;
//    b%=M;
    while (b){
        if (b&1) ret=ret*a%M;
        b>>=1;
        a=a*a%M;
    }
    return ret;
}
//const long double eps=-1.0;
//clock_t t1 = clock();
//fprintf(stderr, "%ld ms\n", clock() - t1);
void open()
{
    freopen("in2.txt","r",stdin);
    freopen("out2.txt","w",stdout);
}
int n;
int a[1005];
vector<int>an;
ll an1,an2;
int lo;
int main()
{
    scanf("%d",&n);
    lo=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]>a[lo])lo=i;
    }
    if(a[lo]<0)
    {
        printf("%d\n",a[lo]);
        printf("%d\n",n-1);
        for(int i=n;i>lo;i--)printf("%d\n",i);
        for(int i=1;i<lo;i++)puts("1");
        return 0;
    }
    for(int i=1;i<=n;i+=2)if(a[i]>0)an1+=a[i];
    for(int i=2;i<=n;i+=2)if(a[i]>0)an2+=a[i];
    if(an1<an2)
    {
        printf("%lld\n",an2);
        if(n&1)an.pb(n--);
        an.pb(1);
        int i;
        for(i=2;i<=n&&a[i]<0;i+=2)an.pb(1),an.pb(1);
        for(i+=2;i<=n;i+=2)
        {
            if(a[i]>0)
                an.pb(2);
            else {an.pb(3);if(i==n)an.pb(2);}
        }
    }
    else
    {
        printf("%lld\n",an1);
        int i;
        if((n&1)==0)an.pb(n--);
        for(i=1;i<=n&&a[i]<0;i+=2)an.pb(1),an.pb(1);
        for(i+=2;i<=n;i+=2)
        {
            if(a[i]>0)
                an.pb(2);
            else {an.pb(3);if(i==n)an.pb(2);}
        }
    }
    printf("%d\n",an.size());
    for(int u:an)printf("%d\n",u);
    return 0;
}

/*
4
1 2 3 2
*/



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

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 60;

int main() {
  int K, N;
  cin >> N >> K;


  vector< int > tap[100000];
  for(int i = 0; i < N; i++) {
    int t, d;
    cin >> t >> d;
    --t;
    tap[t].emplace_back(d);
  }

  vector< int64 > que1, que2;
  for(int i = 0; i < N; i++) {
    sort(tap[i].rbegin(), tap[i].rend());
    if(tap[i].size()) {
      for(int j = 0; j < 1; j++) {
        que1.emplace_back(tap[i][j]);
      }
      for(int j = 1; j < tap[i].size(); j++) {
        que2.emplace_back(tap[i][j]);
      }
    }
  }

  sort(que1.rbegin(), que1.rend());
  sort(que2.rbegin(), que2.rend());
  for(int i = 1; i < que2.size(); i++) {
    que2[i] += que2[i - 1];
  }
  int64 ret = 0, make = 0;
  for(int i = 0; i < K && i < que1.size(); i++) {
    make += que1[i];
    int64 rest = K - i - 1;
    if(rest <= que2.size()) {
      int64 odd = rest <= 0 ? 0 : que2[rest - 1];

      ret = max(ret, make + odd + 1LL * (i + 1) * (i + 1));
    }
  }

  cout << ret << endl;
}


Measured memory_bytes: 6904
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>

using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define debug(x) cout<<#x<<": "<<x<<endl
#define MOD 1000000007

typedef long long ll;
typedef unsigned long long ull;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}
template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

int main(void)
{
    const int MAX_N = 50;
    const int MAX_X = 50;
    int N, A;
    int x[MAX_N];
    cin >> N >> A;
    REP(i, N) cin >> x[i];
    // dp[i][j][k]はx[0],...,x[i]までのカードの中からj枚選び，カードに書かれた整数の合計がkになるような選び方の総数.
    ll dp[MAX_N][MAX_N + 1][MAX_N * MAX_X + 1];

    REP(k, N * MAX_X + 1) {
        dp[0][1][k] = x[0] == k;
    }
    REP(i, N) {
        REP(k, N * MAX_X + 1) {
            dp[i][0][k] = k == 0;
        }
    }
    FOR(i, 1, N) {
        FOR(j, 1, i + 2) {
            REP(k, N * MAX_X + 1) {
                dp[i][j][k] = dp[i - 1][j][k];
                if (x[i] <= k) {
                    dp[i][j][k] += dp[i - 1][j - 1][k - x[i]];
                }
            }
        }
    }
    ll ret = 0;
    FOR(j, 1, N + 1) {
        ret += dp[N - 1][j][j * A];
    }
    cout << ret << endl;
    return 0;
}


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

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

template<typename M,typename N=M>struct SegmentTree{
   using F=function<M(M,M)>; using G=function<M(M,N)>;
   int sz; vector<M> data; const F f; const G g; const M m1;
   SegmentTree(int n,const F f,const G g,const M &m1):f(f),g(g),m1(m1){
      sz=1; while(sz<n)sz<<=1; data.assign(2*sz,m1);
   }
   void build(vector<M> v){
      rep(i,0,v.size())data[i+sz]=v[i];
      for(int k=sz-1;k>0;k--)data[k]=f(data[2*k],data[2*k+1]);
   }
   void update(int k,const N &x){
      k+=sz; data[k]=g(data[k],x);
      while(k>>=1)data[k]=f(data[2*k],data[2*k+1]);
   }
   M query(int a,int b){
      M L=m1,R=m1;
      for(a+=sz,b+=sz;a<b;a>>=1,b>>=1){
         if(a&1)L=f(L,data[a++]);
         if(b&1)R=f(data[--b],R);
      } return f(L,R);
   }
   M operator[](const int &k)const{return data[k+sz];}
};

typedef pair<int,int> P;
typedef pair<int,P> T;

int main(){
   int n; cin>>n;
   vector<int> a(n); rep(i,0,n)cin>>a[i];
   SegmentTree<P> even(n,
   [](P a,P b){return min(a,b);},
   [](P a,P b){return b;},{inf,inf}),
   odd(n,[](P a,P b){return min(a,b);},
   [](P a,P b){return b;},{inf,inf});
   rep(i,0,n){
      if(i&1)odd.update(i,{a[i],i});
      else even.update(i,{a[i],i});
   }
   priority_queue<T,vector<T>,greater<T>> pq;
   auto push=[&](int lb,int rb){
      if(lb==rb)return;
      pq.push({(lb&1?odd.query(lb,rb):even.query(lb,rb)).first,{lb,rb}});
   };
   push(0,n); vector<int> res;
   while(!pq.empty()){
      P p=pq.top().second; pq.pop();
      int lb=p.first,rb=p.second;
      int i1=(lb&1?odd.query(lb,rb):even.query(lb,rb)).second;
      int i2=(lb&1?even.query(i1,rb):odd.query(i1,rb)).second;
      res.push_back(a[i1]); res.push_back(a[i2]);
      push(lb,i1); push(i1+1,i2); push(i2+1,rb);
   }
   rep(i,0,n)cout<<res[i]<<" ";
   return 0;
}

Measured memory_bytes: 11916
#include<stdio.h>

int f[45] = {0};

int fibonacci(int n) {
    if (n == 0 || n == 1) f[n] = 1;
    if (f[n] != 0) return f[n];
    return f[n] = fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    int n, t;
    
    scanf("%d", &n);
    t = fibonacci(n);
    printf("%d\n",t);
    return 0;
}

Measured memory_bytes: 1820
N,M=map(int,input().split())
city=[]
for i in range(M):
    p,y=map(int,input().split())
    city.append([i,p,y])

city.sort(key = lambda t:t[2])
city.sort(key = lambda t:t[1])

id=1
old_city=0
for city_id in city:
    if city_id[1]!=old_city:
        id=1
    city_id[2]=id
    id+=1
    old_city=city_id[1]

city.sort(key = lambda t:t[0])

for x in city:
    ans=x[1]*1000000+x[2]
    print("{0:012d}".format(ans))


Measured memory_bytes: 24492
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<random>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
constexpr auto INF = 1000000000;
constexpr auto LLINF = 1LL << 62;
constexpr auto mod = 1000000007;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }

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

    int n;
    cin >> n;
    VI a(n);
    FOR(i, 0, n)cin >> a[i];

    ll p = 0, m = 0, sum = 0;

    FOR(i, 0, n) {
        sum += a[i];
        if (i % 2) {
            p += max(0LL, 1 + sum);
            chmin(sum, -1LL);
        }
        else {
            p += max(0LL, 1 - sum);
            chmax(sum, 1LL);
        }
    }
    sum = 0;
    FOR(i, 0, n) {
        sum += a[i];
        if (i % 2) {
            m += max(0LL, 1 - sum);
            chmax(sum, 1LL);
        }
        else {
            m += max(0LL, 1 + sum);
            chmin(sum, -1LL);
        }
    }
    cout << min(p, m) << "\n";
}

Measured memory_bytes: 640