uva10261-Ferry-Loading

#include <bits/stdc++.h> 
using namespace std;
bool debug = true;
int test, len, temp, n = 0;
int cars[205], dp[205][10005]; // remaining space on port and starboard
int trace[205][10005], sum[205];
 
int main() {
    //ifstream cin("ferry-loading.inp");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> test;
    while (test--) {
    	n = 0; cars[n] = 0;
    	cin >> len; len *= 100;
 
	while (cin >> temp && temp != 0) {
		cars[++n] = temp;
		sum[n] += sum[n-1] + temp;
	}
	for (int i = 0; i <= n + 5; i++) 
	{ fill(trace[i], trace[i]+len+5, -2); fill(dp[i], dp[i]+len+5, 0); }
	int maxCar = 1; bool done = false;
	dp[0][0] = 1;
	for (int c = 0; c <= n && !done; c++) {
		for (int l = 0; l <= len && !done; l++) {
			if (dp[c][l]==1) {
				bool ok = false;
	    			if (l + cars[c] <= len) {
	    				dp[c+1][l+cars[c]] = 1;
	    				trace[c+1][l+cars[c]] = 0;
	    				ok = true;
	    				if (debug) cout << c+1 << ", " << l+cars[c] << ", " << sum[c-1]-l << ", trace: 0" << "\n";
	    			} 
	    			if (sum[c-1]-l+cars[c] <= len) {
	    				dp[c+1][l] = 1;
	    				trace[c+1][l] = 1;
	    				ok = true;
	    				if (debug) cout << c+1 << ", " << l << ", " << sum[c-1]-l+cars[c] << ", trace: 1" << "\n";
	    			}
	    			if (ok) maxCar=c; 
	    			else done = true;
	     		}
	     	}
	     }
	     cout << maxCar << "\n";
	     int curLen = 0;
	     for (int i = 1; i <= maxCar; i++) {
	     	if (curLen + cars[i] <= len) {
	     		curLen += cars[i];
	     	} 
	     	if (trace[i+1][curLen] == 0) cout << "starboard" << "\n";
	     	else cout << "port" << "\n";
	     }
	}
    return 0;
}