akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
main(){for(int X,Y,f[15][15],d[15][15],i,j;std::cin>>X>>Y,X;printf("%d\n",Y)){for(i=0;i<Y;i++)for(j=0;j<X;d[i][j++]=i==0)std::cin>>f[i][j];for(i=1;i<Y;i++)for(j=0;j<X;j++){!f[i-1][j]&&(d[i][j]+=d[i-1][j]);if(f[i][j]-2){j+1<X&!f[i-1][j+1]&&(d[i][j]+=d[i-1][j+1]);j>0&!f[i-1][j-1]&&(d[i][j]+=d[i-1][j-1]);}i>1&f[i-2][j]==2&&(d[i][j]+=d[i-2][j]);}for(Y=j=0;j<X;j++){f[i-1][j]-1&&(Y+=d[i-1][j]);i>1&f[i-2][j]==2&&(Y+=d[i-2][j]);}}}

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

int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++){
    if(n == 1){
      cout << 1 << endl;
      break;
    }
    if(i*i > n){
      cout << (i-1)*(i-1) << endl;
      break;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int sum=0,ans=0;
	string a;
	cin>>a;
	for(int i=0;i<=a.size()-1;i++)
	{
		if(i%2==0&&a[i]=='1')
		{
			sum++;	
		}
		else if(i%2==1&&a[i]=='0')
		{
			 sum++;	
		}
	}	
	for(int i=0;i<=a.size()-1;i++)
	{
		if(i%2==0&&a[i]=='0')
		{
			ans++;	
		}
		else if(i%2==1&&a[i]=='1')
		{
			ans++;
		}
	}
	cout<<min(ans,sum);	
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 25;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };


string _str[ 7 ] = { "null", "one pair", "two pair", "three card", "straight", "full house", "four card" };
int ans = 0;
int _hand[ 5 ];

int main() {
	while ( ~scanf( "%d,%d,%d,%d,%d", &_hand[ 0 ], &_hand[ 1 ], &_hand[ 2 ], &_hand[ 3 ], &_hand[ 4 ] ) ) {
		ans = 0;
		sort( _hand, _hand + 5 );
		bool is_straight = true;
		for ( int i = 0; i < 4; i++ ) {
			if ( _hand[ i + 1 ] - _hand[ i ] != 1 ) {
				is_straight = false;
				break;
			}
		}
		if ( is_straight ) {
			ans = 4;
		}
		for ( int i = 0; i < 5; i++ ) {
			if ( _hand[ i ] == 1 ) {
				_hand[ i ] += 13;
			}
		}
		sort( _hand, _hand + 5 );
		is_straight = true;
		for ( int i = 0; i < 4; i++ ) {
			if ( _hand[ i + 1 ] - _hand[ i ] != 1 ) {
				is_straight = false;
				break;
			}
		}
		if ( is_straight ) {
			ans = 4;
		}

		bool is_three_card = false;
		bool is_one_pair = false;
		for ( int i = 1; i <= 20; i++ ) {
			int many = upper_bound( _hand, _hand + 5, i ) - lower_bound( _hand, _hand + 5, i );
			if ( many == 4 ) {
				ans = 6;
				break;
			}
			if ( many == 3 ) {
				is_three_card = true;
				ans = 3;
				if ( is_one_pair ) {
					ans = 5;
					break;
				}
			}
			if ( many == 2 ) {
				if ( is_one_pair ) {
					ans = 2;
					break;
				}
				if ( is_three_card ) {
					ans = 5;
					break;
				}
				is_one_pair = true;
				ans = 1;
			}
		}
		printf( "%s\n", _str[ ans ].c_str() );
	}
	return 0;
}

Measured memory_bytes: 1212
program AGC41_A
  integer(8)::N,A,B
  read(*,*)N,A,B
  if((B-A)/2*2==B-A) then
     write(*,*)(B-A)/2
  else
     if(B-A==1) then
        if(A+B<2*N-A-B+2) then
           write(*,*)A
        else
           write(*,*)N-B+1
        end if
        go to 10
     end if
     if(A+B<2*N-A-B+2) then
        write(*,*)(A+B-1)/2
     else
        write(*,*)(2*N-A-B+1)/2
     end if
 10 end if
end program AGC41_A

Measured memory_bytes: 256
def main():
    input()
    a = list(map(int, input().split()))
    ans = 1
    for el in a:
        if el == 0:
            print(0)
            return
    for el in a:
        ans *= el
        if ans > 1e18:
            print(-1)
            return
    else:
        print(ans)


if __name__ == "__main__":
    main()


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

class Point{
public:
    int i;
    int j;
    
    // constructor
    Point(int i,int j) : i(i),j(j) {}
};

class Roads{
    int a;
    int b;
    std::vector<Point> stop;    // intersections that are closed for construction work
    
public:
    // constructor
    Roads(int a,int b) : a(a),b(b) {}
    void setStop(Point p){
        if ( p.i > 0 && p.i < a+1 && p.j > 0 && p.j < b+1 ) {
            stop.push_back(p);
        }
    }
    /* @param (si,sj) - the start point
     * @return - number of choice
     */
    int choice(const int si,const int sj);
};

int Roads::choice(const int si,const int sj){
    // in case (si,sj) is closed.
    auto isStoped = std::find_if(stop.begin(),stop.end(),
                                 [&](Point p){
                                     if (p.i == si && p.j == sj) {
                                         return true;
                                     }else{
                                         return false;
                                     }
                                 }
                                 );
    if (isStoped != stop.end()) {
        return 0;
    }
    
    // in case (si,sj) is not closed.
    if ( si > a-1 ){
        if( sj > b-1) {
            return 1;
        }else{
            return choice(si,sj+1);
        }
    }else{
        if ( sj > b-1 ) {
            return choice(si+1,sj);
        }else{
            return choice(si+1,sj) + choice(si,sj+1);
        }
    }
}

int main(){
    while (true) {
        int a,b;
        std::cin >> a >> b;
        if (a==0 && b==0) {
            return 0;
        }
        
        Roads r(a,b);
        int n;  // number of colsed intersection.
        std::cin >> n;
        // register closed intersections.
        for (int i=0; i < n; ++i) {
            int xi,yi;
            std::cin >> xi >> yi;
            Point p(xi,yi);
            r.setStop(p);
        }
        
        // output.
        std::cout << r.choice(1,1) << std::endl;
    }
    
    return 0;
}

Measured memory_bytes: 3012
using System;
using System.IO;
using System.Linq;

namespace ABC141
{
    class Program
    {
        static void Main()
        {
            var input = Console.ReadLine().Split(' ').Select(int.Parse);
            var N = input.First();
            var K = input.Skip(1).First();
            var Q = input.Skip(2).First();

            var A = new int[Q];
            for (int i = 0; i < Q; i++)
                A[i] = int.Parse(Console.ReadLine());

            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var player = Enumerable.Repeat(K - Q, N).ToArray();
            for (int i = 0; i < Q; i++) player[A[i] - 1]++;

            for (int i = 0; i < N; i++)
                Console.WriteLine(player[i] > 0 ? "Yes" : "No");

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 17736
#include <bits/stdc++.h>
using namespace std;
int main(){
	auto rotate = [](string s){
		return s[s.size()-1] + s.substr(0,s.size()-1);
	};

	string s,t; cin >> s; cin >> t;
	int i = s.size();
	while(i-- > 0){
		s = rotate(s);
//		cout << s << endl;
		if(s==t){
			cout << "Yes" << endl;
			return 0;
		}
	}

   cout << "No" << endl;
   return 0;
}



Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
ans = 0
odd = 0

for i in range(n):
  if a[i] < 0:
    odd += 1
    a[i] = abs(a[i])
  ans += a[i]

if odd%2==1:
  print(ans-2*min(a))
else:
  print(ans)

Measured memory_bytes: 15020
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll a,b;
	cin>>a>>b;
	ll ans=max(a+b,max(a-b,a*b));
	cout<<ans;
}

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

int main() {
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    pair<double, double> p = {cos(M_PI * (h + m / 60) / 6) * a, sin(M_PI * (h + m / 60) / 6) * a};
    pair<double, double> q = {cos(M_PI * m / 30) * b, sin(M_PI * m / 30) * b};
    pair<double, double> diff = {p.first - q.first, p.second - q.second};
    double ans = sqrt(diff.first * diff.first + diff.second * diff.second);
    cout << setprecision(12) << ans << endl;
}

Measured memory_bytes: 4092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
//#define int ll

// const int md = 1000000007;
const int INF = 1<<30;

int main(){
    ll n, x, m;
    cin >> n >> x >> m;
    vector<ll> s(m + 1,-1);
    ll prev = x;
    ll nv = 0;
    s[prev] = x;
    bool f = false;
    ll cnt = 0;
    rep(i, n-1)
    {
        nv = (prev * prev) % m;
        cnt++;
        if (s[nv] != -1)
        {
            f = true;
            break;
        }
        s[nv] = nv + s[prev];
        prev = nv;
    }
    if (!f)
    {
        cout << s[prev] << endl;
        return 0;
    }
    ll loop = 0;
    ll ans = s[nv] - nv;
    ll lf = nv;
    prev = nv;
    rep(i, n)
    {
        ll nv = (prev * prev) % m;
        loop++;
        if (nv == lf)
        {
            break;
        }
        prev = nv;
    }

    ll d = cnt - loop;
    ll k = (n - d) % (loop);
    
    ll cum;
    if (loop == 1){
        cum = nv;
    }else{
        cum = s[prev] - s[nv] + nv;
    }
    //cout << loop << endl;
    ans += cum * (((n - d) / loop));
    rep(i,k){
        ll nv = (prev * prev) % m;
        ans += nv;
        prev = nv;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4016
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...)  Type __VA_ARGS__; input(__VA_ARGS__)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
inline i64  sigma(i64 n)            { return (n * (n + 1) >> 1); }
inline i64  updiv(i64 a, i64 b)     { return (a + b - 1) / b; }
inline i64  sqr(i64 n)              { return n * n; }
inline string to_string(char c)     { return string(1, c); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

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

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

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

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

template <typename Func>
struct FixPoint : Func {
    inline constexpr FixPoint(Func &&f) noexcept : Func(forward<Func>(f)) {}

    template <typename... Args>
    inline decltype(auto) operator()(Args &&... args) const {
        return Func::operator()(*this, forward<Args>(args)...);
    }
};

template< typename Func >
inline decltype(auto) makeFixPoint(Func &&f) {
    return FixPoint< Func >{forward< Func >(f)};
}
// }}} End Header

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

    var(int, a, b);
    print(max({a + b, a * b, a - b}));

    return 0;
}


Measured memory_bytes: 256
import io.StdIn.readLine


object Main {

  def main(args: Array[String]): Unit = {
    val Array(n, t) = readLine().split(' ').map(_.toInt)
    val a = readLine().split(' ').map(_.toInt)

    var tmp = 0
    val b = (a.reverse.map { x =>
      if (x > tmp) tmp = x
      tmp
    }).reverse
    val rew = (1 to (n - 1)).groupBy(i => b(i - 1) - a(i - 1))
    println(rew(rew.keys.max).length)
  }

}


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

using namespace std;

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

int main(){
	int n,m;
	cin>>n>>m;
	
	int sum[101000]={0};
	reps(i,n-1){
		cin>>sum[i];
	}
	
	reps(i,n-1){
		sum[i]=sum[i-1]+sum[i];
	}
	
	
	
	int ans=0;
	int now=0;
	
	rep(i,m){
		int a;
		cin>>a;
		
		int val = sum[now]-sum[now+a];
		if(val<0)val*=-1;
		
		ans+=val;
		now+=a;
		
		ans%=100000;
		
		//printf("%d %d %d %d\n",i,now,val,ans); 
	}
	
	printf("%d\n",ans);
}

Measured memory_bytes: 1236
#include<bits/stdc++.h>
using namespace std;
bool flag;
int main()
{
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='C')
		{
			flag=true;
		}
		if(s[i]=='F'&&flag==true)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

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

int main() {
	int a,b,c;
	cin >>a>>b>>c;
	if(a<=b && b<=c && a<=c){
		cout<< a << " " << b << " " << c <<endl;
	}
	else if(a<=c && c<=b && a<=b){
		cout<< a << " " << c << " " << b <<endl;
	}
	else if(b<=a && a<=c && b<=c){
		cout<< b << " " << a << " " << c <<endl;
	}
	else if(b<=c && c<=a && b<=a){
		cout<< b << " " << c << " " << a <<endl;
	}
	else if(c<=a && a<=b && c<=b){
		cout<< c << " " << a << " " << b <<endl;
	}
	else if(c<=b && b<=a && c<=a){
		cout<< c << " " << b << " " << a <<endl;
	}
}

Measured memory_bytes: 3052
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 3000000000000000000;

int main() {
    int D;
    cin >> D;
    vector<int> c(26);
    rep(i, 26) cin >> c[i];
    vector<vector<int>> s(D, vector<int>(26));
    rep(i, D) rep(j, 26) cin >> s[i][j];
    vector<int> t(D);
    rep(i, D) {
        cin >> t[i];
        --t[i];
    }
    vector<int> last(26, -1);
    int score = 0;
    rep(i, D) {
        score += s[i][t[i]];
        last[t[i]] = i;
        rep(j, 26) score -= c[j] * (i - last[j]);
    }
    vector<set<int>> S1(26), S2(26);
    rep(i, D) {
        S1[t[i]].insert(i);
        S2[t[i]].insert(-i);
    }
    rep(i, 26) {
        S1[i].insert(-1);
        S2[i].insert(1);
        S1[i].insert(D);
        S2[i].insert(-D);
    }
    int M;
    cin >> M;
    rep(i, M) {
        int d, q;
        cin >> d >> q;
        --d; --q;
        score -= s[d][t[d]];
        score += s[d][q];
        int x = *(S2[t[d]].upper_bound(-d));
        x *= (-1);
        int y = *(S1[t[d]].upper_bound(d));
        score += c[t[d]] * (d - x - 1) * (d - x) / 2;
        score += c[t[d]] * (y - d - 1) * (y - d) / 2;
        score -= c[t[d]] * (y - x - 1) * (y - x) / 2;
        x = *(S2[q].upper_bound(-d));
        x *= (-1);
        y = *(S1[q].upper_bound(d));
        score += c[q] * (y - x - 1) * (y - x) / 2;
        score -= c[q] * (d - x - 1) * (d - x) / 2;
        score -= c[q] * (y - d - 1) * (y - d) / 2;
        S1[t[d]].erase(d);
        S2[t[d]].erase(-d);
        S1[q].insert(d);
        S2[q].insert(-d);
        t[d] = q;
        cout << score << "\n";
    }
    return 0;
}


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

typedef long long ll;
 
int main(){
  int n;
  cin >> n;
  int a[n]={};
  for(int i=0; i<n; i++){
    int b;
    cin >> b;
    b--;
    if(b==i) a[i] = 1;
  }
  int ans=0;
  for(int i=0; i<n; i++){
    if(a[i]==1){
      if(i==n-1){
        ans++;
        continue;
      }
      if(a[i+1]==1){
        ans++;
        a[i+1] = 0;
      }else{
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
#define vall(x) (x).begin(), (x).end()
using namespace std;
using lli = long long int;
void YESNO(bool), YesNo(bool);
template <class T1, class T2>
bool chmin(T1 &l, const T2 &r);
template <class T1, class T2>
bool chmax(T1 &l, const T2 &r);
template <class T1, class T2>
void vadd(vector<T1> &v, T2 x);

#define int long long int
vector<lli> dp[5005];
void solve(long long N, long long K, std::vector<long long> a)
{
  vector<lli> b;
  rep(i, N) if (a[i] < K) b.push_back(a[i]);
  sort(b.begin(), b.end());
  lli up = b.size(), low = -1;
  // up is need, low is no need
  N = b.size();
  while (up - low > 1)
  {
    lli mid = (up + low) / 2;
    rep(i, N + 1) dp[i]
        .assign(K, 0);
    dp[0][0] = true;
    rep(i, N)
    {
      rep(j, K)
      {
        dp[i + 1][j] |= dp[i][j];
        if (mid != i && j + b[i] < K)
        {
          dp[i + 1][j + b[i]] |= dp[i][j];
        }
      }
    }
    bool ok = false;
    rrep(i, K)
    {
      if (dp[N][i])
      {
        if (i + b[mid] >= K)
          ok = true;
        break;
      }
    }
    (ok ? up : low) = mid;
  }
  cout << low + 1 << endl;
}

signed main()
{
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  std::vector<long long> a(N);
  for (int i = 0; i < N; i++)
  {
    scanf("%lld", &a[i]);
  }
  solve(N, K, std::move(a));
  return 0;
}

// -- lib
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }

template <class T1, class T2>
bool chmin(T1 &l, const T2 &r)
{
  return (l > r) ? (l = r, true) : false;
}

template <class T1, class T2>
bool chmax(T1 &l, const T2 &r)
{
  return (l < r) ? (l = r, true) : false;
}

template <class T1, class T2>
void vadd(vector<T1> &v, T2 x)
{
  for (auto &s : v)
    s += T2(x);
}


Measured memory_bytes: 195840
#include <iostream>
#include <string>


int main()
{

  while(true){
    std::string str;
    std::cin >> str;
 
    if(str.size()==1 && str == "0")
      break;
 
    int sum =0;
    for(int i=0; i<str.size(); i++){
      sum += str[i] - '0';
    }
      std::cout << sum << std::endl;
  }
}

Measured memory_bytes: 1192
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                if j - idx == 1:
                    cnt = 10 ** 6
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(max(0, -(-x // k)-1))
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(max(0, -(-x // k)-1))
else:
    print(ans)

Measured memory_bytes: 50524
#include<bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
int main(){
  while(1){
    int d,e;
    cin>>d>>e;
    if(d==0&& e==0) break;
    double x=d,y=0,che=1;
    double ans=100000;
    while(y<=x){
      if(sqrt(x*x+y*y)-e<0) che=-1;
      else che=1;
      if((sqrt(x*x+y*y)-e)*che<ans)
	ans=(sqrt(x*x+y*y)-e)*che;
      y++;
      x--;
    }
    cout<<ans<<endl;
  }
  return 0;
}
  


Measured memory_bytes: 3252
#include <bits/stdc++.h>
using namespace std;
#define rep for(int i = 0;i<n;i++)
#define ll long long
 
//const int INF = 1e8;
const int MOD = 1000000007;
typedef pair<int,int>P;
int dx[4] = {1,0,-1,0};int dy[4] = {0,1,0,-1};
queue<P> que;
 
int main(){
    int n;cin >> n;
    int a[n];rep{
        cin >> a[i];
    }
    sort(a,a+n);
    int ans = 0;
    int i = 0;
    while(i<=n-1){
        int sum = 1;
        while(a[i]==a[i+1]){
            sum +=1;
            i++;
        }
        if(sum > a[i]){
            ans += sum -a[i];
        }else if(sum != a[i]){
            ans += sum;
        }
        i++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
  int W, a, b;
  cin >> W >> a >> b;
  int x = 0;
  if (b - a > W || a - b  > W){
  if (a < b && a + W != b)
    x = b - (a + W);
  else if (a > b && a != b + W)
    x = a - (b + W);
  }
  cout << x << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
using namespace std;
using namespace atcoder;
using P = pair<int, int>;
using mint = modint998244353;
typedef long long ll;
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 int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const mint inv9 = mint(1) / 9;

struct S {
  mint x, w;
  S(mint x = 0, mint w = 1): x(x), w(w){}
};

S op(S l, S r) {
  return S(l.x * r.w + r.x, l.w * r.w);
}
S e() { return S(); }

S mapping(int f, S a){
  if(f == 0) return a;
  return S((a.w - 1) * inv9 * f, a.w);
}

int composition(int f, int g){
  if(f == 0) return g;
  return f;
}

int id() {
  return 0;
}

int main() {
  int n, q;
  cin >> n >> q;
  lazy_segtree<S, op, e, int, mapping, composition, id> seg(n);
  rep(i, n){
    seg.set(i, S(1, 10));
  }
  rep(i,q){
    int l, r, d;
    cin >> l >> r >> d;
    --l;
    seg.apply(l, r, d);
    S ans = seg.prod(0,n);
    printf("%d\n", ans.x.val());
  }
}

Measured memory_bytes: 9892
#include <iostream>
#include <string>
using namespace std;
int main()
{
  string s;
  cin>>s;
  int YYMMflag=0,MMYYflag=0;
  int _1=(int)s[0]%48,_2=(int)s[1]%48,_3=(int)s[2]%48,_4=(int)s[3]%48;
  int s_1=_1*10+_2,s_2=_3*10+_4;
   	if(s_1>0 && s_1<=12)
   		MMYYflag=1;
   	if(s_2>0 && s_2<=12)
   		YYMMflag=1;
   	if(MMYYflag==1 && YYMMflag==1)
   		cout<<"AMBIGUOUS"<<endl;
   	if(MMYYflag==0 && YYMMflag==0)
   		cout<<"NA"<<endl;
   	if(MMYYflag==1 && YYMMflag==0)
   		cout<<"MMYY"<<endl;
   	if(MMYYflag==0 && YYMMflag==1)
   		cout<<"YYMM"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#define rep(i,N) for(int i=0;i<(int)N;i++)
#define swap(a,b) (a+=b,b=a-b,a-=b)
const int MOD=1e9+7;
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline void Radix32(int *a,const int sz)
{
  int x,shift=0,elem[256],temp[sz];
  while(shift<32)
  {
    int bucket[256]={0};
    rep(i,sz){x=(a[i]>>shift)&255;bucket[x]++;temp[i]=a[i];}
    elem[0]=0;rep(i,255)elem[i+1]=elem[i]+bucket[i];
    rep(i,sz){x=(temp[i]>>shift)&255;a[elem[x]]=temp[i];elem[x]++;}
    shift+=8;
  }
}
int main()
{
  int N=IN(),K=IN(),l,m=0,r,accum=1,sign=1,A[N];long x,y;
  rep(i,N)A[i]=IN(),m+=A[i]<0?1:0;
  Radix32(A,N);
  rep(i,m/2)swap(A[N-m+i],A[N-1-i]);
  rep(i,(N-m)/2)swap(A[i],A[N-m-1-i]);
  rep(i,N/2)swap(A[i],A[N-1-i]);
  if(K&1)accum=A[N-1],sign=(A[N-1]<0?-1:1),N--,K--;
  l=0,r=N-1;
  while(K)
  {
    x=1l*A[l]*A[l+1],y=1l*A[r]*A[r-1];
    if(x*sign>y*sign)x%=MOD,accum=1l*accum*x%MOD,l+=2;
    else y%=MOD,accum=1l*accum*y%MOD,r-=2;
    K-=2;
  }
  return printf("%ld\n",(1l*accum%MOD+MOD)%MOD),0;
}

Measured memory_bytes: 3132
#include<map>
#include<set>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
	map<int,int> cnt[2];
	set<int> idset[2];
	char s[64];
	int month=0;
	while(cin.getline(s,64)){
		if(s[0]=='\0'){
			month=1;
			continue;
		}

		int id;
		sscanf(s,"%d,%*d",&id);
		cnt[month][id]++;
		idset[month].insert(id);
	}

	vector<int> intersect;
	set_intersection(idset[0].begin(),idset[0].end(),
					 idset[1].begin(),idset[1].end(),
					 inserter(intersect,intersect.begin()));

	for(int i=0;i<intersect.size();i++){
		int id=intersect[i];
		cout<<id<<" "<<cnt[0][id]+cnt[1][id]<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m,v[maxn],fa[maxn];
long long cnt[maxn][2],res;
vector<int> g[maxn];
int p1, p2, len;
void dfs(int x,  int d = 0) {
	++ cnt[x][d & 1];
	for (int u=0;u< g[x].size();++u) {
		if (g[x][u] ==fa[x]) continue;
		if (x == p1 && g[x][u] == p2) continue;
		if (x == p2 && g[x][u] == p1) continue;
		fa[g[x][u]]=x;
		dfs(g[x][u], d + 1);
		cnt[x][0] += cnt[g[x][u]][0];
		cnt[x][1] += cnt[g[x][u]][1];
		res += abs(cnt[g[x][u]][0] - cnt[g[x][u]][1]);
	}
}
void dfs2(int x, int p = 0) {
	v[x] = v[p] + 1;
	for (int u=0;u< g[x].size();++u) {
		if (g[x][u] == p) continue;
		if (v[g[x][u]]) {
			p1 = x;
			p2 = g[x][u];
			len = v[x] - v[g[x][u]] + 1;
		}
		else dfs2(g[x][u], x);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++ i) {
		int u, v;
		
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	if (m == n - 1) {
		dfs(1);
		long long ans = res;
		if (cnt[1][0] != cnt[1][1]) return 0 * puts("-1");
		printf("%lld\n", ans);
	}
	else {
		dfs2(1);
		dfs(1);
		if (len & 1) {
			if (abs(cnt[1][0] - cnt[1][1]) & 1) return 0 * puts("-1");
			long long del = (cnt[1][0] - cnt[1][1]) / 2;
			memset(cnt, 0, sizeof(cnt));
			cnt[p1][0] -= del;
			cnt[p2][0] -= del;
			res=0;
			dfs(1);
			long long ans = res+ abs(del);
			printf("%lld\n", ans);
		}
		else {
			if (cnt[1][0] != cnt[1][1]) return 0 * puts("-1");
			long long l = - 1e9, r = 1e9, ans = 1e18;
			while (l + 10 <= r) {
				long long midl = (l + r) / 2;
				long long midr = (midl + r) / 2;
				memset(cnt, 0, sizeof(cnt));
				cnt[p1][0] += midl;
				cnt[p2][1] += midl;
				res=0;
				dfs(1,0);
				long long res1 = res+abs(midl);
				memset(cnt, 0, sizeof(cnt));
				cnt[p1][0] += midr;
				cnt[p2][1] += midr;
				res=0;
				dfs(1,0);
				long long res2 = res+abs(midr);
				ans = min(ans, res1);
				ans = min(ans, res2);
				if (res1 < res2) {
					r = midr - 1;
				}
				else {
					l = midl + 1;
				}
			}
			for (int i = l; i <= r; ++ i){
				memset(cnt,0,sizeof(cnt));
				cnt[p1][0]+=i;
				cnt[p2][1]+=i;
				res=0;
				dfs(1,0);
				ans = min(ans, res+abs(i));
			}
			printf("%lld\n", ans);
		}
	}
}


Measured memory_bytes: 15872
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		while(true){
			int n = in.nextInt();
			if(n==0)break;
			team[] list = new team[n];
			for(int s=0;s<n;s++){
				list[s]=new team(in.next());
				for(int i=0;i<n-1;i++){
					int a = in.nextInt();
					if(a==0)list[s].win++;
					else if(a==1)list[s].lose++;
					else list[s].hiki++;
				}
			}
			Arrays.sort(list);
			for(int i=0;i<list.length;i++)System.out.println(list[i].name);
		}
	}
}
class team implements Comparable<team>{
	int win,lose,hiki;
	String name;
	team(String name){
		this.name=name;
		win=0;
		lose=0;
		hiki=0;
	}
	public int compareTo(team o) {
		if(this.win>o.win)return -1;
		else if(this.win<o.win)return 1;
		else if(this.lose<o.lose)return -1;
		else if(this.lose>o.lose)return 1;
		return 0;
	}
}

Measured memory_bytes: 23368
#pragma GCC optimize (3)
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define PII pair<int,int>
#define ll long long
using namespace std;
const double PI = acos(-1.0);
const double eps = 1e-6;
int n,m;
char maze[2002][2002];
int row[2002][2002];
int col[2002][2002];
int read()
{
    char ch=getchar();
    int x=0;
    while(ch>'9' || ch<'0') ch=getchar();
    while(ch<='9' && ch>='0') x=x*10+ch-'0',ch=getchar();
    return x;
}
int dfs(int i,int j)
{
    int ccol=0,rrow=0;
    if(j-1>=1 && maze[i][j-1]=='.' && row[i][j-1]!=-1) rrow=row[i][j]=row[i][j-1];
    else{
        for(int j1=j;j1>=1;j1--){
            if(maze[i][j1]=='.') rrow++;
            else break;
        }
        for(int j2=j;j2<=m;j2++){
            if(maze[i][j2]=='.') rrow++;
            else break;
        }
    }
    if(i-1>=1 && maze[i-1][j]=='.' && row[i-1][j]!=-1) ccol=col[i][j]=col[i-1][j];
    else{
        for(int i1=i;i1>=1;i1--){
            if(maze[i1][j]=='.') ccol++;
            else break;
        }
        for(int i2=i;i2<=n;i2++){
            if(maze[i2][j]=='.') ccol++;
            else break;
        }
    }
    row[i][j]=rrow;
    col[i][j]=ccol;
    return ccol+rrow;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) scanf("%s",maze[i]+1);
    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) printf("%c",maze[i][j]);
        printf("\n");
    }*/
    memset(row,-1,sizeof(row));
    memset(col,-1,sizeof(col));
    int ans=-1;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(maze[i][j]=='.') ans=max(ans,dfs(i,j)+1);
    printf("%d\n",ans-4);
    return 0;
}


Measured memory_bytes: 35456
var
	n,m,i,a,b:Longint;
	used:array[1..8]of Boolean;
	c:array[1..8]of Longint;
	G:array[1..8,1..8]of Longint;
function f(u,cnt:Longint):Longint;
var i,ret:Longint;
begin
	if cnt=n then begin
		f:=1;
		exit;
	end;
	ret:=0;
	for i:=1 to c[u] do begin
		if not used[G[u,i]]then begin
			used[G[u,i]]:=True;
			inc(ret,f(G[u,i],cnt+1));
			used[G[u,i]]:=False;
		end;
	end;
	f:=ret;
end;
begin
	read(n,m);
	for i:=1 to m do begin
		read(a,b);
		inc(c[a]);
		inc(c[b]);
		G[a,c[a]]:=b;
		G[b,c[b]]:=a;
	end;
	used[1]:=True;
	writeln(f(1,1));
end.

Measured memory_bytes: 128
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
	int k;
	cin >> k;
	
	if (k % 2 == 0) {
		cout << k * k /4 << endl;
	}
	else {
		cout << k / 2 * (k / 2 + 1) << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <utility>
#include <tuple>
#include <random>
using namespace std;

const double pi = acos(-1);
#define nyan cout << "(=^•ω•^=)" << endl;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define repn(n) while(n--)
#define loop while(true)
#define YN(f) f?cout<<"YES"<<endl:cout<<"NO"<<endl;
#define yn(f) f?cout<<"Yes"<<endl:cout<<"No"<<endl;

int ans;
int cnt;

signed main(){
	string s;cin>>s;
	for(int i=0;i<s.length();i++){
		if(s[i]=='W'){
			ans+=i-cnt;
			cnt++;
		}
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
char s[65536],t[65536];
main(n,i,r,w,c)
{
	for(;scanf("%d",&n),n;puts(s))
		for(i=!scanf("%s",s);i++<n;t[w]=0,strcpy(s,t))
			for(r=w=0;r<strlen(s);t[w++]=s[r],r+=c){
				for(c=0;s[++c+r]==s[r];);
				for(sprintf(t+w,"%d\0",c);t[++w];);
			}
}

Measured memory_bytes: 492
#include <stdio.h>
#include <string.h>


int main(void)
{

	int len1, len2, len3;
	char str1[11], str2[11], str3[11];

	
	scanf(" %s %s %s", &str1, &str2, &str3 );
	len1 = strlen(str1);
	len2 = strlen(str2);
	len3 = strlen(str3);
	
	if(str1[len1-1]==str2[0] && str2[len2-1]==str3[0]  ) printf("YES\n");
	else { printf("NO\n");}



	//getchar();
	//getchar();
	return 0;
}


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

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> M;
typedef vector<int> V;
typedef queue<int> Q;
typedef pair<long,long> PLL;
typedef map<long,long> MLL;
typedef vector<long long> VLL;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
/*--------------------------------------------*/
ll gcd(ll a,ll b){
    while(b!=0) {
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}
VLL divisor(ll n){//約数の列挙o(√n)
    VLL res;
    for(ll i=1;i*i<=n;i++) {
        if(n%i == 0){
        res.push_back(i);
        if(i!=n/i)res.push_back(n/i);
        }
    }
    return res;
}
int main(){
    int a,b,k;cin>>a>>b>>k;
    int m=gcd(a,b);
    VLL ans=divisor(m);
    sort(RALL(ans));
    cout<<ans[k-1]<<endl;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
D = {}
for _ in range(N):
  a, b = map(int, input().split())
  if a not in D: D[a] = 0
  D[a] += b

D = sorted(list(D.items()))
k = 0
for a, b in D:
  k += b
  if k>=K:
    print(a)
    exit()

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



int main(){
  int N,K;
  cin>>N>>K;
  
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    int A;
    cin>>A;
    vec.at(A-1)+=1;
  }
  sort(vec.begin(),vec.end());
  
  int sum=0;
  for(int i=0;i<N-K;i++){
    sum+=vec.at(i);
  }
  cout<<sum<<endl; 
  
}

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

int main() {
  long long Q, H, S, D, N;
  cin >> Q >> H >> S >> D >> N;
  cout << (N / 2) * min(8 * Q, min(4 * H, min(2 * S, D))) +
              (N % 2) * min(4 * Q, min(2 * H, S))
       << endl;
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort(reverse = True)
    ans = A[0]
    for i in range(n-2):
        ans += A[i//2 + 1]
    print(ans)

if __name__=='__main__':
    main()

Measured memory_bytes: 31420
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

  int p, q, r;
  cin >> p >> q >> r;
  cout << min({p + q, r + q, p + r});
}


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

int main()
{
    int n, p, s;
    char x[1];
    vector<int> md;
    vector<int> d;
    scanf("%d %d\n", &n, &p);
    vector<int> c(p, 0);
    string xx;
    cin >> xx;
    int64_t ans = 0;
    if (10 % p == 0)
    {
        rep(i, n)
        {
            if ((xx[i] - '0') % p == 0)
            {
                ans += i + 1;
            }
        }
    }
    else
    {
        int ten = 1;
        vector<int> c(p, 0);
        c[0]++;
        int s = 0;
        rep(i, n)
        {
            s += ((xx[n - i - 1] - '0') * ten) % p;
            s %= p;
            ans += c[s];
            c[s]++;
            ten *= 10;
            ten %= p;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"
template<class T> void chmax(T &a, const T b){ a = max(a, b); }
template<class T> void chmin(T &a, const T b){ a = min(a, b); }

const ll inf = LONG_LONG_MAX / 2 - 1;
ll n;
vector<ll> a;
vector<vector<ll>> dp;

ll dfs(ll l, ll r) {
    if (dp[l][r] != inf) return dp[l][r];
    ll turn = n - (r - l + 1);
    if (turn % 2 == 0) {
        if (l == r) {
            dp[l][r] = a[l];
            return dp[l][r];
        }
        dp[l][r] = -inf;
        chmax(dp[l][r], dfs(l + 1, r) + a[l]);
        chmax(dp[l][r], dfs(l, r - 1) + a[r]);
    }
    else {
        if (l == r) {
            dp[l][r] = -a[l];
            return dp[l][r];
        }
        dp[l][r] = inf;
        chmin(dp[l][r], dfs(l + 1, r) - a[l]);
        chmin(dp[l][r], dfs(l, r - 1) - a[r]);
    }
    return dp[l][r];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    cin >> n;
    a.resize(n);
    rep(i, n) cin >> a[i];
    dp.resize(n, vector<ll>(n, inf));
    cout << dfs(0, n - 1) << endl;
    return 0;
}


Measured memory_bytes: 73948
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower

using namespace std;

int main() {
	vector<long long> COUNT(200000, 0);
	vector<long long> SUM(200000, 0);
	int N;
	cin >> N;

	long long GRANDTTL = 0;

	for (int i = 0; i < N; i++) {
		int Ai;
		cin >> Ai;
		SUM.at(Ai) += Ai;
		COUNT.at(Ai)++;
		GRANDTTL += Ai;
	}

	int Q;
	cin >> Q;

	for (int i = 0; i < Q; i++) {
		int Bi, Ci;
		cin >> Bi >> Ci;
		long long X, Y;
		X = COUNT.at(Bi);
		Y = SUM.at(Bi);

		GRANDTTL = GRANDTTL - Y + X * Ci;

		SUM.at(Bi) = 0;
		SUM.at(Ci) += X * Ci;

		COUNT.at(Bi) = 0;
		COUNT.at(Ci) += X;

		cout << GRANDTTL << endl;
	}
}

Measured memory_bytes: 6220
#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<int, lli> il;
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;}

#ifdef LOCAL
#define eprintf(...) printf(__VA_ARGS__)
#else 
#define eprintf(...) 1
#endif

#define ROUNDUP(a, b) 		( ((a) + ((b) - 1) ) / b)
#define SET_ZERO(a)	 		( memset((a), 0, sizeof(a)))
#define SET_NUM_ARRAY(a,b)	( memset((a), b, sizeof(a)))

int main() {
	int N, T;
	cin >> N >> T;
	int A[100009];
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	int min = 1000000009;
	int max = -1;
	int minindex = 0;
	int cnt = 0;
	for (int i = 1; i < N; i++) {
		int d = A[i] - A[minindex];
		if (d > 0) {
			if (d == max) {
				cnt++;
			} else if (d > max) {
				max = d;
				cnt = 1;
			}
		}
		if (chmin<int>(min, A[i])) {
			minindex = i;
		}
	}
	printf("%d\n", cnt);
	return 0;
}


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

int main(void){
  int N, Z, W; cin >> N >> Z >> W;
  vector<int> a(N);
  for(auto& _a: a) cin >> _a;
  if(N == 1) cout << abs(a[0] - W) << endl;
  else cout << max(abs(a[N-1]-W), abs(a[N-1]-a[N-2])) << endl;
}
	

Measured memory_bytes: 256
import java.util.*;

import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		int N = Integer.parseInt(tokens[0]);
		int K = Integer.parseInt(tokens[1]);

		List<Integer> h = new ArrayList<>(N);
		tokens = in.readLine().split(" ");
		for (int i = 0; i < N; ++i) {
			h.add(Integer.parseInt(tokens[i]));
		}
		Collections.sort(h);
		Collections.reverse(h);
		int count = 0;
		for (int i = 0; i < N; ++i) {
			if (h.get(i) < K) {
				break;
			}
			++count;
		}
		System.out.println(count);
	}
}


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

using namespace std;

int main()
{
    int A, B;
    cin >> A >> B;
    int rem = 16 - min(A, B) * 2;
    int more = abs(A - B);
    if (rem >= more * 2)
    {
        cout << "Yay!" << endl;
    }
    else
    {
        cout << ":(" << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int a,b,x;
    char op;
    cin >> a >> op >> b;
    while(op!='?'){
        if ( op == '+' ){x=a+b;}
        else if ( op == '-' ){x=a-b;} 
        else if ( op == '*' ){x=a*b;}
        else if ( op == '/' ){x=a/b;}
        cout << x << endl;
        cin >> a >> op >> b;
    }return 0;
}


Measured memory_bytes: 3080
#include <iostream>

 

using namespace std;

 

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if(a <= b && b <= c)
        cout << a << " " << b << " " << c << endl;
    else if(a <= c && c <= b)
        cout << a << " " << c << " " << b << endl;
    else if(b <= a && a <= c)
        cout << b << " " << a << " " << c << endl;
    else if(b <= c && c <= a)
        cout << b << " " << c << " " << a << endl;
    else if(c <= a && a <= b)
        cout << c << " " << a << " " << b << endl;
    else cout << c << " " << b << " " << a << endl;
}


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

int main(void)
{
    long n,a[200000],i,j,k,as[200000],suml,sumr,p,q,r,s,ans,temp,max,min,maxl,minl,maxr,minr;

    scanf("%ld",&n);
    for ( i = 0; i < n; i++)
    {
        scanf("%ld",a+i);
    }
    
    for ( i = 0; i < n; i++)
    {
        if(i==0) as[0]=a[0];
        else as[i]=as[i-1]+a[i];
    }

    ans=as[n-1];

    i=0;
    k=2;
    for(j=1;j<=n-3;j++)
    {
        suml=as[j];
        for(;i<=j-1;i++)
        {
            if(as[i]>=(suml+1)/2) break;
        }
        if(i!=0&&labs(as[i-1]-suml/2)<=labs(as[i]-(suml+1)/2)) i--;

        sumr=as[n-1]-as[j];
        if(j>=k) k=j+1;
        for(;k<=n-2;k++)
        {
            if(as[k]-as[j]>=(sumr+1)/2) break;
        }
        if(k!=j+1&&labs(as[k-1]-as[j]-sumr/2)<=labs(as[k]-as[j]-(sumr+1)/2)) k--;

        p=as[i];q=as[j]-as[i];r=as[k]-as[j];s=as[n-1]-as[k];
        maxl=(p>q)? p:q;
        minl=(p<q)? p:q;
        maxr=(r>s)? r:s;
        minr=(r<s)? r:s;
        max=(maxl>maxr)? maxl:maxr;
        min=(minl<minr)? minl:minr;
        temp=max-min;
        if(ans>=temp) ans=temp;
    }

    printf("%ld",ans);

    return 0;
}

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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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; }


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

    vector<string> S(N);
    rep(i,N) cin >> S[i];

    sort(all(S));
    rep(i,S.size()) cout << S[i];
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;



int main(){
  int N;
  cin>>N;
  int M=N%1000;
  if(M){
    cout<<1000-M<<endl;
  }else{
    cout<<0<<endl;

  }
  return 0;

} 


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 200009;

int n, k, tot, a[N];
LL ans, sum[N], val[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Fenwick_Tree{
	int cnt[N];
	public:
		inline void modify(int x) {
			for (int i = x; i <= tot; i += lowbit(i)) {
				cnt[i]++;
			}
		}
		inline int query(int x) {
			int ret = 0;
			for (int i = x; i; i -= lowbit(i)) {
				ret += cnt[i];
			}
			return ret;
		}
}BIT;

inline int id(LL x) {
	int l = 1, r = tot, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (val[mid] == x) {
			return mid;
		} else if (val[mid] < x) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
}

int main() {
#ifdef DBG
	freopen("11input.in" , "r", stdin);
#endif
	n = read(); k = read();
	val[++tot] = 0;
	for (int i = 1; i <= n; ++i) {
		a[i] = read() - k;
		sum[i] = sum[i - 1] + a[i];
		val[++tot] = sum[i];
	}
	sort(val + 1, val + 1 + tot);
	tot = unique(val + 1, val + 1 + tot) - val - 1;
	//cout<<"YES"<<endl;
	BIT.modify(id(0));
	for (int i = 1; i <= n; i++) {
		ans += BIT.query(id(sum[i]));
		BIT.modify(id(sum[i]));
	}
	cout<<ans<<endl;
 	return 0;
}

// p_r - p_l >= 0
// p_r >= pl

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

int main()
{
    char s1[3];
    char s2[3];

    for (int i = 0; i < 3; i++)
    {
        cin >> s1[i];
    }
    for (int i = 0; i < 3; i++)
    {
        cin >> s2[i];
    }

    if (s1[0] == s2[2] && s1[1] == s2[1] && s1[2] == s2[0])
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 256